UVA10827 Maximum sum on a torus WA

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

UVA10827 Maximum sum on a torus WA

Post by LanceHAOH » Sun Dec 25, 2016 6:08 pm

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

Post by lighted » Fri Mar 10, 2017 1:50 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”