TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

55.6% (15/27)

Tags

Description

妁艷和楓音來到了深夜的操場.

經過了剛才的敵襲, 妁艷又成功地救了楓音.

不知何時, 兩人已經牽起了手, 像一對人人看了都會羨慕的情侶一般. (攻略成功了)

深夜的天空, 群星閃耀. 夜空持續增加兩人的連結.

走到了庭院花園中, 此刻兩人的同步率已經達到400%.(what?)

他們現在急需躺在花園草坪上一片較空曠的地方欣賞夜景, 以免雜草小石子太多破壞氣氛.

庭院花園是一個NxM的矩形, 每一塊單位正方形有一個邪魔度, 代表躺在這裡有多不舒服.

身為愛神厄洛斯的你, 必須在花園草坪上找一片平行花園長寬的矩形, 裡面的邪魔度總和≤R, 並且面積越大越好, 讓兩人能以各種符合人體工學的姿態欣賞夜空.

Input Format

第1行有三個正整數N, M, R, (1≤N, M, R≤1,000), 意義如上文所述.
第i+1行的第j個數字為一個正整數Jij, 表示此單位正方的邪魔度為Jij (1≤Jij≤1,000).

Output Format

輸出唯一的數字, 代表符合上文所述的最大矩形面積.

Sample Input

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

Sample Output

4

Hints

選擇左上角的2x2矩形, 和為8, 不超過9.

Problem Source

原TIOJ1762 / problem setter: willyliu

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8