Cod sursa(job #490523)

Utilizator cosmyoPaunel Cosmin cosmyo Data 6 octombrie 2010 18:49:18
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
int sm,a,s[305][305],n,m,p;
using namespace std;

int main()
{int i,j,k,lst=0;
 ifstream fin("teren.in");
 ofstream fout("teren.out");

  fin>>n>>m>>p;
   for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
     {fin>>a;
      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;
     }
 for(i=n;i>=1;--i)
 {lst=0;
    for(j=1;j<=m;++j)
        {if(s[i][j]-s[i][lst]<=p)
            {if(i*(j-lst)>sm)
              sm=i*(j-lst);
            }
           else
            {for(k=lst+1;k<=j;++k)
             if(s[i][j]-s[i][k]<=p)
              {lst=k;
               if(i*(j-lst)>sm)
                sm=i*(j-lst);break;
              }
            }

        }
 }

 fout<<sm<<'\n';

 fin.close();
 fout.close();

 return 0;
}