UVA10827 Maximum sum on a torus WA

[LanceHAOH]

I wrote a O(n^4) solution for UVA10827. It passes all the tests on udebug and the ones that I can find from past threads on this problem. Unfortunately, I am still getting WA. Is anyone able to come up with a counterexample for my algorithm?

Code: Select all

#include <iostream>
#include <algorithm>
using namespace std;

int sum[200][200];
int cc,r,c,a,R,C,INF = 9999;
int tmax,gmax,srow;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> cc;
    while(cc--) {
        cin >> r;
        c = r;
        R = C = 2 * r;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                scanf("%d",&a);
                sum[i+1][j] = a;
                sum[i+1][c+j] = a;
                sum[i+r+1][j] = a;
                sum[i+r+1][c+j] = a;
            }
        }
        for(int j = 0; j < R; j++) {
            for(int i = 0; i < C; i++) {  
                sum[j+1][i] += sum[j][i];
            }
        }
        gmax = -INF;
        for(int i = 1; i < r+1; i++) {
            for(int j = i; j < i+r; j++) {
                for(int m = 0; m < c; m++) {
                    tmax = 0;
                    for(int k = m; k < c + m; k++) {
                        srow = sum[j][k] - sum[i-1][k];
                        tmax = max(srow,tmax+srow);
                        gmax = max(gmax,tmax);
                    }
                }
            }
        }
        cout << gmax << endl;
    }
    return 0;
}

[lighted]

Try to post in existing thread. Remove line or set value to true.

Code: Select all

ios_base::sync_with_stdio(false);