1762 . Ch2. Section 7. 遙仰半月的夜空
TopCoder
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 1
3 3 9
1 2 3
2 3 4
3 4 5
1 2 3
2 3 4
3 4 5
Sample Output 1
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 |