Cod sursa(job #156126)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 12 martie 2008 13:00:42
Problema Sum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#define N 111
int mat[N][N]={{0}},bat[N][N]={{0}};
int main()
  {
   int n,i,j,t,k,s=0,max=-112;
   freopen("joctv.in", "r",stdin);
   freopen("joctv.out", "w",stdout);
   scanf("%d", &n);


   for(i=1;i<=n;++i)
	for(j=1;j<=n;++j)
		scanf("%d", &mat[i][j]);
   bat[1][1]=mat[1][1];
   for(i=1;i<=n;++i)
	for(j=1;j<=n;++j)
		bat[i][j]=bat[i-1][j]+bat[i][j-1]-bat[i-1][j-1]+mat[i][j];

   for(i=1;i<=n;++i)
    {
      s=0;
      for(j=1;j<=n;++j)
       {
	 bat[i][j]=mat[i][j];
	 s+=mat[i][j];
	 if(s>max) max=s;
	 if(s<0) s=0;
	}
	 for(t=i+1;t<=n;++t)
	 {
	  s=0;
	   for(j=1;j<=n;++j)
	     {
	     bat[t][j]=bat[t-1][j]+mat[t][j];
	     s+=bat[t][j];
	     if(s>max)
		 max=s;
	     if(s<0) s=0;
	     }
	     }
	    }
   printf("%d", max);
   return 0;
}