VOI 18 Bài 4 - Phần thưởng - VNOJ: VNOI Online Judge

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

Points: 0.50 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

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

Vinh là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty AZ tài trợ. Trên mỗi ô của một lưới kích thước ~n \times n~ ô vuông có cạnh độ dài đơn vị, Ban tổ chức xếp một món quà. Các dòng của bảng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới và các cột của bảng được đánh số từ ~1~ đến ~n~, từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~ và món quà trên ô đó có giá trị là ~a_{ij}~ ~(1 \le i, j \le n)~.

Ban tổ chức cho phép Vinh chọn một trong ~k~ phương án nhận phần thưởng. Phần thưởng trong phương án thứ ~s~ ~(s = 1, 2, \dots, k)~ được xác định như sau: Vinh được nhận các món quà trên các ô của lưới thuộc một trong ~p~ hình vuông kích thước ~r \times r~, trong đó hình thứ ~h~ xác định bởi ô góc trên trái có tọa độ ~(x_{sh}, y_{sh})~, ~h = 1, 2, \dots, p~. Chú ý là các hình vuông này nằm trọn vẹn trong lưới và có thể có các hình vuông là 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

Dòng thứ nhất chứa bốn số nguyên dương ~n~, ~k~, ~r~, ~p~;
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ là ~a_{ij}~ ~(a_{ij} \le 10^6)~, ~(i =1, 2, \ldots, n~; ~j = 1, 2, \ldots, n)~;
Dòng thứ ~s~ trong số ~k~ dòng tiếp theo chứa ~2 \times p~ số nguyên dương ~x_{s1}, y_{s1}, x_{s2}, y_{s2}, \ldots, x_{sp}, y_{sp}~ xác định ~p~ hình vuông trong phương án thứ ~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

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~n \le 50~; ~k \le 50~; ~p \le 5~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 2~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 3~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có ~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

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:

Comments

Please read the guidelines before commenting.

-10

tronghuy commented on Dec. 25, 2023, 9:01 a.m. ← edited →

xin lỗi mn acc mình bị phá

This comment is hidden due to too much negative feedback. Show it anyway.