Cod sursa(job #292304)

Utilizator klamathixMihai Calancea klamathix Data 30 martie 2009 23:28:10
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#include<algorithm>

#define MAXN 301

using namespace std;

int i , j, k, N , M , X ,  A[MAXN][MAXN] , counts[MAXN][MAXN], v[MAXN], maxs, S , right , left;
//bool ok;

int main()
{
    FILE*in=fopen("teren.in","r");
    FILE*out=fopen("teren.out","w");
    
    fscanf(in ,"%d %d %d",&N ,&M ,&X);
    
    for( i = 1; i <= N ; i++)
     for( j = 1; j <= M ; j++)
     {
      fscanf(in,"%d",&A[i][j]);
      if(i == 1) counts[i][j] = A[i][j];
     }
     
      for( i = 2; i <= N ; i++)
       for( j = 1; j <= M ; j++)
        counts[i][j] = counts[i-1][j] + A[i][j];
 
     for( i = 1; i <= N ; i++)
      for( j = i + 1; j <= N ; j++)
           {
            for( k = 1 ; k <= M ; k++)
                    v[k] = counts[j][k] - counts[i - 1][k];
           
           left = 1;
           S = 0;
           for( right = 1 ; right <= M ; right++)
           {
                S += v[right];
                while(left <= right && S > X)
                {
                           S -= v[left];
                           left++;
                }
                
                if((j-i+1)*(right-left+1) > maxs) maxs =(j-i+1)*(right-left+1);
           }
           } 
           
 fprintf(out,"%d\n",maxs);
 
 return 0;
}