I. Pirate Chest

2013 World Finals St. Petersburg HOSTED BY ITMO Problem I Pirate Chest Time Limit: 15 seconds Pirate Dick finally had enough of fighting, marauding, theft, and making life miserable for many on the open seas. So he decided to retire, and he found the perf...

Updated May 21, 2026

Track ICPC

Year 2013

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 15 seconds

Pirate Dick finally had enough of fighting, marauding, theft, and making life miserable for many on the open seas. So he decided to retire, and he found the perfect island to spend the rest of his days on, provided he does not run out of money. He has plenty of gold coins now, and he wants to store them in a chest (he is a pirate after all). Dick can construct a rectangular chest with integer dimensions of any size up to a specified maximum size for the top but with an arbitrary integer height. Now he needs a place to hide the chest. While exploring the island, he found the perfect solution. Dick will hide his chest by submerging it in a murky pond. The pond has a rectangular surface, and it completely fills the bottom of a valley that has high vertical rocky walls. Dick surveyed the pond and knows its depth for each of the squares of a Cartesian coordinate grid system placed on the pond surface. When Dick submerges the chest, it will sink as far as possible until it touches the bottom. The top of the chest will remain parallel to the pond’s surface and the chest will be aligned with the grid squares. The water displaced by the submerged chest will raise the level of the pond’s surface (this will occur even if there is no space around the chest for the displaced water to rise). The walls of the valley are high enough that the water can never splash out of the valley. Of course, since the chest must be invisible, its top must be strictly below the surface of the pond. Your job is to find the volume of the largest chest that Pirate Dick can hide this way. In Figure I.1, the leftmost image shows a pond, the middle image shows a possible placement of a chest of volume 3, and the rightmost image shows a placement of a chest of volume 4, which is the maximum possible volume. Note that if the second chest were made one unit taller, its top would be visible because it would be at exactly the same height as the surface of the water.

Figure I.1: Illustration of Sample Input 1.

Input

The input consists of a single test case. A test case starts with a line containing four integers a, b, m, and n (1 ≤ a, b, m, n ≤ 500). The pond’s surface dimensions are m × n and the maximum size of the top (and bottom) of the chest is a × b. In addition, a and b are small enough that it is not possible to cover the entire pond with a chest with top size a × b. Each of the remaining m lines in a test case contains n integers di,j specifying the pond’s depth at grid square (i, j), where 0 ≤ di,j ≤ 109 for each 1 ≤ i ≤ m and 1 ≤ j ≤ n.

                                                             ICPC 2013
2013 World Finals
                                                       St. Petersburg
                                                        HOSTED BY   ITMO

Output

Display the maximum volume of a rectangular chest with integer dimensions (where one of the dimen- sions of the top is bounded by a and the other is bounded by b) that can be completely submerged below the surface of the pond. If no chest can be hidden in the pond, display 0.

Sample Tests

Sample 1

Sample Input

 3 1 2 3
 2 1 1
 2 2 1

Sample Output

Sample 2

Sample Input

 4 1 1 5
 2 0 2 2 2

Sample Output

Sample 3

Sample Input

 2   3   3   5
 2   2   2   2 2
 2   2   2   2 2
 2   2   2   2 2

Sample Output

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

#include <bits/stdc++.h>
using namespace std;

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2013/I-pirate-chest/solution.texC++ implementationcompetitive_programming/icpc/2013/I-pirate-chest/solution.cppStatement textcompetitive_programming/icpc/2013/I-pirate-chest/statement.txtStatement PDFcompetitive_programming/icpc/2013/I-pirate-chest/statement.pdfMetadatacompetitive_programming/icpc/2013/I-pirate-chest/meta.jsonYear packetcompetitive_programming/icpc/2013/contest_problems.pdf

I. Pirate Chest

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets