Mai intai trebuie sa te autentifici.
Cod sursa(job #389912)
Utilizator | Data | 2 februarie 2010 14:57:46 | |
---|---|---|---|
Problema | Teren | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.03 kb |
#include<fstream.h>
#include<iostream.h>
#define VMAX 300
int m,n,X,a[VMAX][VMAX];
void read()
{ ifstream f("teren.in");
f>>n>>m>>X;
int i,j,var;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
{
f>>var;
if(i>0)a[i][j]+=a[i-1][j];
a[i][j]+=var;
}
f.close();
}
int MAX(int a,int b)
{
if(a>=b)return a;
return b;
}
int suma(int x1,int y1,int x2,int y2)
{
int i,s=0;
for(i=y1;i<=y2;++i)
if(x1>0)s+=a[x2][i]-a[x1-1][i];
else s+=a[x2][i];
return s;
}
int search(int x,int y)
{
int i=x,j=y,max=0,var,s=0,jCreste=1;
var=(i-x+1)*(j-y+1);
while(i>=x)
{
s=suma(x,y,i,j);
if(s<=X&&j<m&&i<n)
{
if(var>max){max=var;++i;}
else if(jCreste<0)--i;
}
else{--i;j+=jCreste+1;}
if(i==n)
{--i;++j;}
if(j>=m)
{--j;jCreste=-1;}
var=(i-x+1)*(j-y+1);
}
return max;
}
int solve()
{
int i,j,max=0;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
max=MAX(max,search(i,j));
return max;
}
int main()
{
read();
ofstream g("teren.out");
g<<solve();
g.close();
return 0;
}