VO 16 Bài 5 - Chia đất

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
VNOI Online 2016
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Sau khi thương lượng, cuối cùng Phú Ông quyết định sẽ cắt cho Bờm ~2~ khu đất trong quỹ đất của mình để đổi lấy chiếc quạt mo. Quỹ đất của phú ông có dạng ~R~ hàng ngang và ~C~ cột dọt gồm ~R \times C~ thửa. Mỗi thửa có một giá trị kinh tế khác nhau (có thể âm).

Phú Ông đồng ý chia cho Bờm ~2~ khu đất, một khu hình chữ nhật kích thước ~A \times B~ gồm ~A~ hàng ngang và ~B~ cột thửa đất nhỏ (lưu ý ~A \times B~ khác ~B \times A)~; và ~1~ khu đất "hình thoi" kích thước ~K~ sao cho:

  • Hai khu đất Bờm chọn không chứa thửa đất nào chung (không giao nhau).
  • Hai khu đất Bờm chọn phải nằm hoàn toàn trong khu đất của Phú Ông.

Biết rằng khu đất hình thoi với tâm ở thửa ~(x~, ~y)~ và có kích thước ~K~ sẽ là tập hợp các thửa ~(x', y')~ thoả mãn ~|x' - x| + |y' - y| \leq K~. Phú ông cho Bờm lựa chọn tuỳ ý, Bờm cũng bắt đầu giao động trước đề nghị này. Bạn hãy giúp Bờm xác định ~2~ khu đất thoả mãn sẽ có giá trị kinh tế *lớn nhất *là bao nhiêu.

Input

  • Dòng đầu tiên ghi ~5~ số ~R~, ~C~, ~A~, ~B~, ~K~.
  • Tiếp theo là ~R~ dòng, mỗi dòng ghi ~C~ số nguyên thể hiện giá trị kinh tế của các thửa đất.

Output

In ra giá trị kinh tế lớn nhất của 2 khu đất mà Bờm có thể chọn. Nếu không có cách chọn 2 khu đất thoả mãn, in ra "no solution".

Giới hạn

Trong tất cả các test, giá trị kinh tế của các thửa đất có trị tuyệt đối không vượt quá 10~^6~.

  • Subtask ~1~ ~(30\%~ số điểm): ~R~, ~C \leq 50~
  • Subtask ~2~ ~(40\%~ số điểm): ~R~, ~C \leq 200~
  • Subtask ~3~ ~(30\%~ số điểm): ~R~, ~C \leq 1000~

Sample Input 1

5 5 2 2 1
1 1 1 1 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
1 1 1 1 1

Sample Output 1

16

Sample Input 2

5 5 2 2 3
1 1 1 1 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
1 1 1 1 1

Sample Output 2

no solution

Note

Giải thích

Ở bộ test đầu tiên Bờm sẽ hời nhất nếu chọn 2 khu đất như sau:

1 1 1 1 1

1 2 2 2 1

1 2 2 2 1

1 2 2 2 1

1 1 1 1 1

Ở bộ test thứ hai Bờm không thể chọn khu đất "hình thoi" kích thước là 3 nào nằm hoàn toàn ở trong khu đất của Phú Ông.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.