//Code by Patcas Csaba #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define PII pair #define VB vector #define VI vector #define VD vector #define VS vector #define VPII vector > #define VVI vector < VI > #define VVB vector < VB > #define FORN(i, n) for(int i = 0; i < (n); ++i) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REPEAT do{ #define UNTIL(x) }while(!(x)); #define SZ size() #define BG begin() #define EN end() #define CL clear() #define X first #define Y second #define RS resize #define PB push_back #define MP make_pair #define ALL(x) x.begin(), x.end() #define in_file "a.in" #define out_file "a.out" #define INF 2000000000 int n; VVI a, sum; int subSum(int i1, int j1, int i2, int j2) { if (i1 > i2 || j1 > j2) return 0; return sum[i2][j2] + sum[i1 - 1][j1 - 1] - sum[i1 - 1][j2] - sum[i2][j1 - 1]; } int main() { //Read data //freopen(in_file, "r", stdin); //freopen(out_file, "w", stdout); cin >> n; a.RS(n + 1, VI(n + 1)), sum.RS(n + 1, VI(n + 1)); FOR(i, 1, n) FOR(j, 1, n) { cin >> a[i][j]; sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; } //Solve int best = -INF; FOR(i1, 1, n) FOR(j1, 1, n) FOR(i2, i1, n) FOR(j2, j1, n) { int borderSum = subSum(i1, j1, i2, j2) - subSum(i1 + 1, j1 + 1, i2 - 1, j2 - 1); best = max(best, borderSum); } //Write data cout << best; return 0; }