-
Notifications
You must be signed in to change notification settings - Fork 1
/
UVa 108.cpp
60 lines (46 loc) · 1.05 KB
/
UVa 108.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define iter(i, a, b) for(int i = (a) ; i < (b) ; i++)
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair< int , int > pii;
typedef pair< int , pii > iii;
typedef vector<int> vi;
typedef vector< pii > vii;
typedef map<int, int> mii;
#define INF (1 << 29)
#define PI (2.0 * acos(0.0))
#define MAXX 1000
int n, a[101][101], subRect, maxSubRect;
int main(){
//READ("UVa 108.txt");
while(scanf("%d", &n) != EOF){
rep(i, n){
rep(j, n){
scanf("%d", &a[i][j]);
if(j > 0)
a[i][j] += a[i][j - 1];
}
}
maxSubRect = -127 * 100 * 100;
rep(l, n){
iter(r, l, n){
subRect = 0;
rep(row, n){
if(l > 0)
subRect += a[row][r] - a[row][l - 1];
else
subRect += a[row][r];
if(subRect < 0)
subRect = 0;
maxSubRect = max(maxSubRect, subRect);
}
}
}
printf("%d\n", maxSubRect);
}
return 0;
}