APIO 2009

Chính phủ Siruseri quyết định đấu giá đất tại tỉnh Navalur giàu dầu mỏ cho các nhà thầu tư nhân xây dựng giếng dầu. Toàn bộ khu vực được đấu giá được chia thành một lưới hình chữ nhật gồm \(M \times N\) ô đất nhỏ.

Cơ quan Khảo sát Địa chất Siruseri có dữ liệu về trữ lượng dầu ước tính ở Navalur. Dữ liệu này được công bố dưới dạng một lưới \(M \times N\) số nguyên không âm, cho biết trữ lượng ước tính trong từng ô đất.

Để ngăn chặn độc quyền, chính phủ quy định mỗi nhà thầu chỉ được đấu giá một khối vuông gồm \(K \times K\) ô đất liền nhau. Liên minh dầu mỏ AoE gồm ba nhà thầu thông đồng với nhau, muốn chọn ba khối không có ô đất chung sao cho tổng trữ lượng dầu trong các khối được chọn là lớn nhất.

AoE thuê bạn viết chương trình xác định tổng trữ lượng dầu ước tính lớn nhất mà họ có thể giành được.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(M\), \(N\) và \(K\), trong đó \(M\), \(N\) lần lượt là số hàng và số cột của lưới, còn \(K\) là độ dài cạnh của khối vuông được phép đấu giá.

Trong \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên không âm mô tả trữ lượng dầu ước tính ở các ô đất trên một hàng.

Dữ liệu ra

In một dòng chứa một số nguyên duy nhất: tổng trữ lượng dầu ước tính lớn nhất mà liên minh AoE có thể giành được.

Ràng buộc

• \(1 \le M, N \le 1500\).
• \(1 \le K \le \min(M,N)\).
• Trữ lượng dầu ước tính trong mỗi ô là một số nguyên từ \(0\) đến \(500\).
• Luôn có thể chọn ít nhất ba khối \(K \times K\) không có ô đất chung.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

208

Nguồn

Asia-Pacific Informatics Olympiad 2009 — Oil (Digging for Oil), đề tiếng Anh phiên bản 1.3.

Chính phủ Siruseri vừa xây dựng một trung tâm hội nghị mới. Nhiều công ty muốn thuê hội trường của trung tâm để tổ chức hội nghị.

Một khách hàng chỉ đồng ý thuê nếu được sử dụng riêng hội trường trong toàn bộ thời gian diễn ra hội nghị của mình. Trưởng bộ phận tiếp thị của trung tâm quyết định cho càng nhiều khách hàng khác nhau thuê càng tốt. Có thể có nhiều cách lựa chọn đáp ứng mục tiêu này.

Các công ty được đánh số theo thứ tự gửi yêu cầu thuê. Một tập yêu cầu được xem là tập ứng viên nếu có số lượng công ty lớn nhất có thể mà không có hai hội nghị nào trùng ngày. Để bảo đảm công bằng, trưởng bộ phận tiếp thị sắp xếp các số hiệu công ty trong mỗi tập ứng viên theo thứ tự tăng dần, rồi chọn danh sách nhỏ nhất theo thứ tự từ điển.

Thứ tự từ điển được định nghĩa như sau: danh sách \(L_1\) nhỏ hơn danh sách \(L_2\) nếu \(L_1\) là tiền tố của \(L_2\), hoặc tại vị trí đầu tiên \(j\) mà hai danh sách khác nhau, ta có \(L_1[j] < L_2[j]\).

Hội trường chỉ có thể được cho một công ty thuê trong mỗi ngày. Ngày bắt đầu và ngày kết thúc đều thuộc thời gian thuê; vì vậy, hai yêu cầu có ngày kết thúc của yêu cầu này bằng ngày bắt đầu của yêu cầu kia không thể cùng được chấp nhận.

Hãy xác định tập công ty được thuê hội trường theo quy tắc trên.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), số công ty đã gửi yêu cầu thuê hội trường.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên là ngày bắt đầu và ngày kết thúc hội nghị của công ty \(i\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(M\), số công ty lớn nhất có thể được thuê hội trường.

Dòng thứ hai chứa \(M\) số nguyên là số hiệu các công ty, viết theo thứ tự tăng dần, trong tập ứng viên nhỏ nhất theo thứ tự từ điển.

Ràng buộc

• \(1 \le N \le 200000\).
• Với mỗi yêu cầu, ngày bắt đầu không nhỏ hơn \(1\), ngày kết thúc không lớn hơn \(10^9\), và ngày bắt đầu không lớn hơn ngày kết thúc.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
4 9
9 11
13 19
10 17

2
1 3

Nguồn

Asia-Pacific Informatics Olympiad 2009 — Convention (The Siruseri Convention Centre), đề tiếng Anh phiên bản 1.1.

Thành phố Siruseri chỉ có đường một chiều. Các con đường gặp nhau tại các giao lộ và theo quy định, tại mỗi giao lộ đều có một máy ATM của Ngân hàng Siruseri. Các quán rượu trong thành phố cũng chỉ nằm ở các giao lộ, nhưng không phải giao lộ nào cũng có quán rượu.

Banditji dự định thực hiện vụ cướp ATM lớn nhất trong lịch sử Siruseri. Anh ta xuất phát từ trung tâm thành phố, lái xe đi cướp tất cả các máy ATM đi qua, rồi kết thúc hành trình tại một quán rượu để ăn mừng.

Nhờ kỹ năng xâm nhập hệ thống của mình, Banditji biết chính xác lượng tiền trong từng máy ATM. Hãy giúp anh ta xác định tổng số tiền lớn nhất có thể cướp được trên một hành trình bắt đầu tại trung tâm thành phố và kết thúc tại một trong các quán rượu.

Banditji được phép đi qua cùng một giao lộ hoặc con đường bao nhiêu lần tùy ý, nhưng luôn phải đi đúng chiều đường. Sau lần ghé thăm đầu tiên, máy ATM tại một giao lộ không còn tiền để lấy nữa.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(M\), lần lượt là số giao lộ và số con đường. Các giao lộ được đánh số từ \(1\) đến \(N\).

Trong \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên thuộc đoạn từ \(1\) đến \(N\), lần lượt là giao lộ xuất phát và giao lộ kết thúc của một con đường một chiều.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên cho biết lượng tiền trong máy ATM tại giao lộ \(i\).

Dòng tiếp theo chứa hai số nguyên \(S\) và \(P\), trong đó \(S\) là giao lộ xuất phát (trung tâm thành phố) và \(P\) là số quán rượu.

Dòng cuối chứa \(P\) số nguyên liệt kê các giao lộ có quán rượu.

Dữ liệu ra

In một số nguyên duy nhất: tổng số tiền lớn nhất Banditji có thể cướp được trên đường đi từ trung tâm thành phố đến một trong các quán rượu.

Ràng buộc

• \(1 \le N, M \le 500000\).
• \(1 \le S \le N\) và \(1 \le P \le N\).
• Lượng tiền tại mỗi máy ATM là số nguyên không âm, không vượt quá \(4000\).
• Luôn có ít nhất một quán rượu có thể đi tới từ trung tâm thành phố theo các con đường một chiều.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4 3 5 6

47

Nguồn

Asia-Pacific Informatics Olympiad 2009 — ATM (The Great ATM Robbery), đề tiếng Anh phiên bản 1.1.