## UVA10827 Maximum sum on a torus WA

Moderator: Board moderators

LanceHAOH
New poster
Posts: 9
Joined: Tue Aug 27, 2013 9:04 am

### UVA10827 Maximum sum on a torus WA

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: UVA10827 Maximum sum on a torus WA

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

Code: Select all

``ios_base::sync_with_stdio(false);``
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman