VOI 18 Bài 4 - Phần thưởng

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đọc đề gốc tại đây

Vinh là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty AZ tài trợ. Trên mỗi ô của một lưới kích thước ~n \times n~ ô vuông có cạnh độ dài đơn vị, Ban tổ chức xếp một món quà. Các dòng của bảng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới và các cột của bảng được đánh số từ ~1~ đến ~n~, từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~ và món quà trên ô đó có giá trị là ~a_{ij}~ ~(1 \le i, j \le n)~.

Ban tổ chức cho phép Vinh chọn một trong ~k~ phương án nhận phần thưởng. Phần thưởng trong phương án thứ ~s~ ~(s = 1, 2, \dots, k)~ được xác định như sau: Vinh được nhận các món quà trên các ô của lưới thuộc một trong ~p~ hình vuông kích thước ~r \times r~, trong đó hình thứ ~h~ xác định bởi ô góc trên trái có tọa độ ~(x_{sh}, y_{sh})~, ~h = 1, 2, \dots, p~. Chú ý là các hình vuông này nằm trọn vẹn trong lưới và có thể có các hình vuông là giao nhau.

Yêu cầu: Hãy giúp Vinh chọn phương án nhận phần thưởng với tổng giá trị của các món quà nhận được là lớn nhất.

Input

  • Dòng thứ nhất chứa bốn số nguyên dương ~n~, ~k~, ~r~, ~p~;
  • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ là ~a_{ij}~ ~(a_{ij} \le 10^6)~, ~(i =1, 2, \ldots, n~; ~j = 1, 2, \ldots, n)~;
  • Dòng thứ ~s~ trong số ~k~ dòng tiếp theo chứa ~2 \times p~ số nguyên dương ~x_{s1}, y_{s1}, x_{s2}, y_{s2}, \ldots, x_{sp}, y_{sp}~ xác định ~p~ hình vuông trong phương án thứ ~s~ ~(s = 1, 2, \ldots, k)~.

Output

Ghi ra một số nguyên duy nhất là giá trị lớn nhất của tổng giá trị các món quà mà Vinh có thể nhận được.

Giới hạn

  • Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~n \le 50~; ~k \le 50~; ~p \le 5~;
  • Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 2~;
  • Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 3~;
  • ~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p \le 5~;

Sample Input

4 2 2 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 2 2 3 3
1 1 1 3 3 1

Sample Output

12

Note

Giải thích:

Các hình vẽ dưới đây mô tả 2 phương án giải thưởng trong ví dụ và tổng giá trị của giải thưởng trong mỗi phương án:

image

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.


There are no comments at the moment.