trang chủ / đề bài / icpcwf13_i

Rương của cướp biển

Đề bài

Mô tả

Cướp biển Dick cuối cùng đã chán cảnh chém giết, cướp bóc, trộm cắp và gieo rắc khổ sở cho bao người trên biển cả. Ông quyết định nghỉ hưu và đã tìm được hòn đảo hoàn hảo để sống nốt quãng đời còn lại, miễn là ông không tiêu hết tiền. Lúc này ông có rất nhiều đồng tiền vàng và muốn cất chúng trong một chiếc rương (dù sao ông cũng là cướp biển). Dick có thể đóng một chiếc rương hình hộp chữ nhật với các kích thước nguyên, mặt trên có kích thước tối đa cho trước nhưng chiều cao là một số nguyên tuỳ ý. Bây giờ ông cần một chỗ để giấu rương. Khi khám phá hòn đảo, ông đã tìm ra giải pháp hoàn hảo.

Dick sẽ giấu rương bằng cách nhấn chìm nó trong một cái ao nước đục. Mặt ao là một hình chữ nhật, nước lấp đầy hoàn toàn đáy một thung lũng có vách đá thẳng đứng rất cao. Dick đã khảo sát cái ao và biết độ sâu tại từng ô vuông của một lưới toạ độ Descartes đặt trên mặt ao. Khi được thả xuống, rương sẽ chìm sâu nhất có thể cho đến khi chạm đáy. Mặt trên của rương luôn song song với mặt ao và rương được đặt thẳng hàng với các ô lưới. Lượng nước bị rương chiếm chỗ sẽ làm mực nước của ao dâng lên (điều này xảy ra kể cả khi xung quanh rương không có chỗ nào cho nước dâng lên). Vách thung lũng đủ cao để nước không bao giờ tràn ra ngoài. Tất nhiên, vì rương phải được giấu kín nên mặt trên của nó phải nằm thấp hơn hẳn mặt nước của ao.

Nhiệm vụ của bạn là tìm thể tích lớn nhất của chiếc rương mà cướp biển Dick có thể giấu theo cách này.

Trong hình dưới đây (ví dụ thứ nhất), hình bên trái là cái ao, hình ở giữa là một cách đặt rương có thể tích 3, hình bên phải là một cách đặt rương có thể tích 4, đây là thể tích lớn nhất có thể. Lưu ý rằng nếu rương thứ hai cao thêm một đơn vị thì mặt trên của nó sẽ bị nhìn thấy, vì khi đó nó nằm đúng ngang mặt nước.

Dữ liệu vào

Dữ liệu gồm một test duy nhất:

  • Dòng đầu chứa bốn số nguyên a, b, m, n. Mặt ao có kích thước m×n, còn mặt trên (và mặt đáy) của rương có kích thước tối đa là a×b. Ngoài ra, a và b đủ nhỏ để một rương có mặt trên kích thước a×b không thể phủ kín toàn bộ mặt ao.
  • m dòng tiếp theo, mỗi dòng chứa n số nguyên di,j: độ sâu của ao tại ô (i,j).

Dữ liệu ra

In ra thể tích lớn nhất của một chiếc rương hình hộp chữ nhật có các kích thước nguyên (một cạnh của mặt trên không vượt quá a và cạnh còn lại không vượt quá b) có thể nhấn chìm hoàn toàn dưới mặt nước của ao. Nếu không thể giấu chiếc rương nào, in ra 0.

Ràng buộc

  • 1≤a,b,m,n≤500.
  • 0≤di,j≤109 với mọi 1≤i≤m, 1≤j≤n.

Ví dụ

Input Output Giải thích
3 1 2 3
2 1 1
2 2 1
4 Ví dụ trong hình. Rương đáy 2×1 đặt trên hai ô sâu 2 ở cột đầu, cao 2: nước dâng thêm 4/6, mặt trên của rương ngang mặt ao ban đầu nên thấp hơn mặt nước mới. Nếu cao 3 thì nước dâng đúng 1, mặt trên ngang mặt nước.
4 1 1 5
2 0 2 2 2
12 Rương đáy 1×3 đặt trên ba ô cuối (độ sâu 2), cao 4: nước dâng thêm 12/5=2,4, mặt trên cao hơn mặt ao ban đầu 2<2,4.
2 3 3 5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
18 Rương đáy 3×2, cao 3: nước dâng thêm 18/15=1,2, mặt trên cao hơn mặt ao ban đầu 1<1,2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0