Nam cùng một nhóm bạn chơi trò chơi giải cứu bong bóng. Có n quả bong bóng, mỗi quả bóng được ghi số nguyên ai , 1 ≤ i ≤ n, là lượng khí mà bong bóng thứ i đang chứa. Khi tới giờ quy định, nếu có 2 quả bóng u, v mà au + av = S thì tất cả các bong bóng sẽ nổ. Biết rằng, trò chơi quy định các bạn chỉ được xả khí của mỗi cặp bong bóng có tổng bằng S. Để chạy đua với thời gian, nhóm của Linh Đan cần nhanh chóng trong thời gian ngắn nhất, khi tới giờ quy định, xả hết khí của một số cặp bong bóng, khi đó các bong bóng còn lại không tạo ra tổng S gây nổ. Thời gian xả khí mỗi cặp bong bóng u, v như vậy là một giây.

Yêu cầu: Hãy xác định thời gian tối thiểu cần thiết để có thể cứu tất cả các bong bóng.

Dữ liệu: Vào từ file văn bản BALLOON.INP gồm:

• Dòng đầu tiên chứa hai số nguyên n và S (1 ≤ n ≤ 10^5 , 1 ≤ S ≤ 10^9 ).
• Dòng thứ hai chứa n số nguyên a1 , a2 , ..., an (1 ≤ ai ≤ 10^9 , 1 ≤ i ≤ n).

Kết quả: Đưa ra file văn bản BALLOON.OUT một số nguyên duy nhất là thời gian tối thiểu cần thiết để cứu tất cả các bong bóng.

Ví dụ:

Input

7 7
4 3 4 8 4 3 4

Output

2

Ràng buộc:

• Subtask 1 (50% số điểm): n ≤ 10^3
• Subtask 2 (50% số điểm): n ≤ 10^5

Để thực hiện chương trình "Bảo vệ môi trường xanh sạch đẹp", tỉnh Đoàn Bình Định đã phát động phong trào trồng cây xanh trên vùng đất trống dành cho đối tượng học sinh. Vùng đất trồng có hình dạng một hình chữ nhật kích thước 10^9 × 10^9 . Khi mới trồng các cây con, học sinh cần che chắn để tránh nắng chiều lên phần diện tích để trồng trọt. Có tất cả n tấm chắn để có thể che chắn vùng đất. Mỗi tấm chắn đều có hình chữ nhật cạnh song song với cạnh của vùng đất, góc dưới trái của tấm chắn đặt ở tọa độ (0, 0), tấm chắn thứ i có tọa độ đỉnh trên phải là (xi , yi). Do hạn chế về mặt kinh phí, tỉnh Đoàn chỉ cho phép học sinh được chọn k tấm chắn để che chắn cho vùng đất.

Yêu cầu: Hãy xác định diện tích lớn nhất có thể được đồng thời bảo vệ bởi k tấm chắn.

Dữ liệu: Vào từ file văn bản TREE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 2 × 10^5 ).
• Dòng thứ i trong n dòng sau chứa hai số nguyên xi , y i (1 ≤ xi , y i ≤ 10^9 )

Kết quả: Đưa ra file văn bản TREE.OUT một số nguyên duy nhất là diện tích lớn nhất được đồng thời bảo vệ bởi k tấm chắn.

Ví dụ:

Input

5 3
3 5
2 2
2 5
4 4
5 3

Output

9

Ràng buộc:

• Subtask 1 (50% số điểm): 1 ≤ k ≤ n ≤ 3 × 10^3

• Subtask 2 (50% số điểm): 1 ≤ k ≤ n ≤ 2 × 10^5

  Bản PDF

Trong ngôi làng nhỏ, có một người nông dân tên là Bình. Bình là một người nông dân có tâm hồn đam mê trồng trọt. Anh muốn đào đất xuống sâu nhất có thể để cây dễ dàng lấy chất dinh dưỡng từ vùng đất sâu. Một ngày nọ, trong lúc làm ruộng, anh phát hiện ra rằng các thửa đất sát nhau có độ cao chênh lệch không quá 1 đơn vị. Vì để dễ trồng, trong quá trình đào đất, anh ta vẫn muốn giữ đúng kết cấu của ruộng (2 thửa đất sát nhau có độ cao chênh lệch không quá 1 đơn vị). Mỗi lần Bình đào một thửa đất xuống 1 đơn vị độ cao thì anh tiêu hao 1 đơn vị sức lực. Khi sử dụng hết sức lực thì anh không thể đào tiếp được nữa. Vậy hỏi, trong ngày hôm nay với M sức lực, Bình có thể đào sâu nhất là bao nhiêu?

Độ cao các thửa đất được biểu thị bởi N số trên một dòng. Hai số liên tiếp có giá trị chênh lệch nhau không quá 1 đơn vị (|hi - hi - 1| ≤ 1 với 2 ≤ i ≤ N và hi là độ cao thửa đất thứ i).

Yêu cầu: Hãy giúp Bình tìm xem với M đơn vị sức lực thì Bình sẽ đào được sâu nhất là bao nhiêu mà vẫn thỏa mãn yêu cầu trên.

Dữ liệu: Vào từ file văn bản FARMER.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương N, M (N ≤ 10^5, M ≤ 10^12) là số thửa đất trên mảnh ruộng và sức lực của Bình trong ngày hôm nay.

• Dòng tiếp theo chứa N số nguyên dương với hi là độ cao thửa đất thứ i (1 ≤ hi ≤ 10^5).

Kết quả: Đưa ra file văn bản FARMER.OUT một số nguyên duy nhất là độ sâu sâu nhất mà Bình có thể đào được.

Ví dụ:

Input

4 3
1 1 1 1

Output

-1

Ví dụ 2:

Input

4 3
1 2 2 1

Output

0

Ràng buộc:

• Subtask 1 (25% số điểm): N, M ≤ 10^3
• Subtask 2 (25% số điểm): N ≤ 10^3, M ≤ 10^8
• Subtask 3 (25% số điểm): N ≤ 10^5, M ≤ 10^12, h1 = h2 = ... = hN
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Bản PDF

Nhà vua vừa mở hội mấy ngày đêm, già trẻ trai gái các làng đều nô nức tham dự. Trên các nẻo đường, quần áo mớ ba mớ bảy dập dìu tuôn về kinh như nước chảy. Hai mẹ con Cám cũng sắm sửa quần áo đẹp để đi trẩy hội. Thấy Tấm cũng muốn đi, mụ dì ghẻ nguýt dài. Sẵn có chén gạo trong góc tường, mụ đổ ra sàn và bắt Tấm phải nhặt từng hạt gạo và bỏ vào hai hũ. Biết rằng chén gạo có đúng K hạt gạo và hạt gạo thứ i khi được bỏ vào hũ thứ nhất sẽ có độ ngon là ai , khi được bỏ vào hũ thứ hai sẽ có độ ngon là bi.

Dì ghẻ yêu cầu Tấm chia đúng N hạt gạo vào hũ thứ nhất và M hạt gạo vào hũ thứ hai sao cho độ ngon là lớn nhất. Số gạo còn dư sẽ được đem đi cho gà trong vườn. Vì số lượng hạt gạo quá nhiều nên Tấm gặp khó khăn trong việc phân loại.

Yêu cầu: Hãy giúp Tấm tính tổng độ ngon lớn nhất khi bỏ gạo vào hai hũ nhé.

Dữ liệu:

• Dòng đầu tiên chứa ba số nguyên dương K, N, M (K ≤ 10^3, N + M ≤ K)
• Dòng thứ i trong K dòng tiếp theo chứa hai số nguyên dương ai, bi (1 ≤ ai, bi ≤ 10^5) là độ ngon tương ứng của hạt thứ i khi bỏ vào hũ thứ nhất và hũ thứ hai.

Kết quả:

Đưa ra một số nguyên duy nhất là tổng độ ngon của các hạt gạo trong hai hũ.

Ví dụ:

Input

4 2 1
4 9
3 5
7 2
5 5

Output

21 

GIẢI THÍCH

• Hũ thứ nhất sẽ chứa hạt gạo thứ 3 và 4 do đó có độ ngon là 7 + 5 = 12.
• Hũ thứ hai sẽ chứa hạt gạo thứ 1 do đó có độ ngon là 9. Tổng độ ngon sẽ là 12 + 9 = 21.

Ràng buộc:

• Subtask 1 (25% số điểm): K ≤ 15
• Subtask 2 (25% số điểm): K, M ≤ 10^3, N = 1
• Subtask 3 (25% số điểm): K ≤ 400
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Bản PDF