oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

climatechange Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

climatechange.html

Problem Description

Climate change has been affecting the entirety of Guan Island recently, with Guan's slave farmers quickly losing arable land to farm to feed Guan's insatiable hunger. Guan Island can be described as a grid of N by M integers, with each integer within a grid representing the height above "sea level" at that point on Guan Island. However, the sea level has started to rise and if the height of the sea is the same or greater than the height of the land, the grid square will be flooded.

Guan's slaves are planning to build a rectangular farm and this farm must be at least of area S square units so as to satisfy Guan. Help calculate what is the maximum sea level rise that can happen for Guan's slaves to still be able to build that farm.

Input

The first line of input will contain three integers, N, M and S.
The next N lines will contain M strictly positive integers each, which describes the varying height of Guan Island.

Output

The output should contain exactly one integer, the maximum sea level rise that can happen for Guan's slaves to still be able to build that farm.

Limits

All integers in the input will be under 1 000 000 000.
Subtask 1 (14%): 1 ≤ N, M ≤ 50.
Subtask 2 (21%): 1 ≤ N ≤ 50. 1 ≤ M ≤ 1 000.
Subtask 3 (3%): 1 ≤ N, M ≤ 1 000. S = 1.
Subtask 4 (62%): 1 ≤ N, M ≤ 1 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

4 5 7
1 3 4 2 3
2 3 4 1 3
2 2 2 3 4
2 4 5 1 3

Sample Output 2

1

Tags

Dynamic Programming, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114201s256MBMinimum
221201s256MBMinimum
33201s256MBMinimum
462201s256MBMinimum
5021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o climatechange -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.