Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BONUS - VOI 2011 Phần thưởng

Tuấn là người chiến thắng 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 XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng một lưới ô vuông kích thước đơn vị. 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à trên ô đó chứa một món quà có giá trị là a[i,j] (1 <= i, j <= n)

Đề nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận được.

Dữ liệu:

  • Dòng thứ nhất chứa hai sô nguyên dương n, k (n <= 1000, n/3 <= k <= n).
  • 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[i,j] (a[i,j] <= 1000)

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

Ví dụ:

Dữ liệu

Kết quả

4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14
86


 

 

 

1

9

1

1

9

9

9

9

1

9

9

9

1

9

9

14

 

 

 

Ràng buộc: 50% số test ứng với 50% số điểm của bài có n <= 100.


Được gửi lên bởi:VOJ Team
Ngày:2011-01-12
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2011

hide comments
2018-10-23 15:14:40
Rất là ghét bọn gay sớm nhá
2018-10-23 14:55:01
1 chút AC <3
2018-10-23 14:54:15
1 đấm AC :D
2018-09-23 08:06:12
mình xin trả lời cmt của bạn mà có đề chọn 2 hình vuông k*k không chồng lên nhau (tại mình vô không được fb bạn), mình hông có đòi quà đâu :v
gọi f[i][j] là tổng các ô trong hcn {(1, 1), (i, j)} -> O(n^2)
gọi h[i][j] là hình vuông k*k có tổng lớn nhất nằm trong hcn{(1, 1), {i, j}) ->O(n^2) h[i][j] = max(h[i-1][j], h[i][j-1], hình vuông có đỉnh phải dưới là (i, j))
cuối cùng duyệt O(n^2) res = max(res, hình vuông hiện tại (có đỉnh phải dưới là (i, j)) + max(h[i-k][j], h[i][j - k])).

Last edit: 2018-09-23 08:09:01
2018-04-03 11:02:48
Bài này dễ quá, đổi đề 1 chút thử thách mọi người:
Chọn 2 hình vuông có kích thước k*k không chồng lên nhau sao cho được tổng phần thưởng lớn nhất.
Bạn nào làm được gửi vào fb cho mình, mình chấm AC thì có thưởng nhé ;)
https://www.facebook.com/quyettzzlczz
2018-03-17 09:25:32
tham khảo : http://123link.pw/q85T5QXF
2017-12-31 07:49:55
nhật hào sạch
2017-11-23 15:50:00
QHĐ đơn giản full điểm
2017-11-10 02:17:52
vãi đề voi luôn
2017-10-06 11:40:29
xin chào các fan hâm mộ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.