108 - Maximum Sum

[brianfry713]

Try the case Jan posted here:
http://online-judge.uva.es/board/viewtopic.php?t=7796

[richard1017]

I test my code on several arrays and got the correct answer. However, the verdict says a WA.
Could you please check my code?
Thank you.

Code removed after AC.

[brianfry713]

Print a newline char at the end of the line.

[richard1017]

Print a newline char at the end of the line.

Thanks, Accepted!

[vilash99]

I used following code. Work fine for given input and my various test inputs. But WA
Please help.....
thanks in advance.
My code:

Removed after AC.

[brianfry713]

What is your algorithm? You can solve this in O(N ^ 5)

[vilash99]

Thanks, for suggestion.
I was trying to get O(N ^ 4) using Kadane algorithms.
Got AC in O(N^5)

[cunbidun]

my code work fine with random test but when i submit still WA
my code:

Code: Select all

#include<stdio.h>
#include<string.h>
int maxx(int a,int b){
    if(a>b) return a;
    else return b;
}

int main(){
     freopen("tongcn1.inp","r",stdin);
     //freopen("tongcn1.out","w",stdout);
    int n,a[125][127],i,j,s[127][127],max[127][127],maxt,k,ma,l   ;
     scanf("%d",&n);
    for(i=0;i<=n;i++)
            s[i][0]=0;
    for(j=0;j<=n;j++)
            s[0][j]=0;
    for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    scanf("%d",&a[i][j]);
                    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
                }
            }
    maxt=a[1][1];

    for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                for(l=0;l<i;l++)
                    for(k=0;k<j;k++)
                {


                        ma=s[i][j]-s[l][j]-s[i][k]+s[l][k];

                        if(ma>maxt) maxt=ma;
                }


            }
    printf("%d",maxt);
}

help please!

[brianfry713]

Don't read from a file.