Pagini recente » Cod sursa (job #1261420) | Cod sursa (job #2113612) | Cod sursa (job #371304) | Cod sursa (job #1006298) | Cod sursa (job #468165)
Cod sursa(job #468165)
#include <stdio.h>
#define lung 300
int N,M,X,S[lung+5][lung+5];
int max;
void citire()
{
int i,j,x;
freopen("teren.in","r",stdin);
scanf("%d%d%d",&N,&M,&X);
for (i=1;i<=N;i++)
{
scanf("%d",&x);
S[1][i]= (i==1) ? x : S[1][i-1]+x;
for (j=2;j<=M;j++)
{
scanf("%d",&x);
S[i][j]= x+ S[i-1][j] + S[i][j-1] - S[i-1][j-1];
}
}
}
int GetQuality(int x1,int y1,int x2,int y2)
{
return S[x2][y2] - (S[x1-1][y2] + S[x2][y1-1] - S[x1-1][y1-1]);
}
int GetMin(int n,int m)
{
int i,j,min,x;
min=-1;
for (i=n;i<=N;i++)
for (j=m;j<=M;j++)
{
x=GetQuality(i-n,j-m,i,j);
if (min==-1 || x<min)
min=x;
}
return min;
}
bool bsearchM(int ls,int ld,int x,int n)
{
int m,xp,r;
r=-1;
while (ls<=ld)
{
m=(ls+ld)/2;
xp=GetMin(n,m);
if (xp<=x)
r= (m>r) ? m : r,
ls=m+1;
else
ld=m-1;
}
max= (n*r>max) ? n*r : max;
return (r>0);
}
void bsearchN(int ls,int ld)
{
int m;
while (ls<=ld)
{
m= (ls+ld)/2;
if (bsearchM(1,M,X,N))
ls=m+1;
else
ld=m-1;
}
}
void scriere()
{
freopen("teren.out","w",stdout);
printf("%d\n",max);
fclose(stdout);
}
int main()
{
citire();
bsearchN(1,N);
scriere();
return 0;
}