Pagini recente » Cod sursa (job #1079379) | Cod sursa (job #2936340) | Cod sursa (job #1735299) | Cod sursa (job #967425) | Cod sursa (job #217679)
Cod sursa(job #217679)
#include <cstdio>
#define Nmax 303
#define Mmax 303
#define precizie 1000
#define ll long long
int N, M, R, C, Amax;
int A[Nmax][Mmax];
int S[Nmax][Mmax];
int i,j;
void citire()
{
freopen("balans.in","r",stdin);
scanf("%d %d %d %d",&N,&M,&R,&C);
for (i=1; i<=N; ++i)
for (j=1; j<=M; ++j)
{
scanf("%d", &A[i][j]);
A[i][M+j] = A[i+N][j] = A[i+N][j+M] = A[i][j];
Amax = Amax > A[i][j] ? Amax : A[i][j];
}
}
void compute()
{
for (i=1; i<=2*N; ++i)
for (j=1; j<=2*M; ++j)
S[i][j] = S[i-1][j] + A[i][j];
}
int exista(int V)
{
int st,dr,k;
ll T, dif;
for (i=0; i<=N-1; ++i)
for (j=i+R; j<=i+N; ++j)
{
st=1;
dr=C;
dif = (ll) V*(j-i);
for (k=1, T=0; k<=C; ++k)
T += (ll) (S[j][k] - S[i][k])*precizie - dif;
if (T>=0) return 1;
while (st<N)
{
++dr;
T += (ll) (S[j][dr] - S[i][dr])*precizie - dif;
while (dr-st>=N)
{
T -= (ll) (S[j][st] - S[i][st])*precizie - dif;
++st;
}
while (T - (S[j][st] - S[i][st])*precizie + dif > T && dr-st>=C)
{
T -= (ll) (S[j][st] - S[i][st])*precizie - dif;
++st;
}
if (T>=0) return 1;
}
}
return 0;
}
void cauta()
{
int p=1, nr=0;
Amax *= precizie;
while ((p << 1)<=Amax) p<<=1;
while (p)
{
if (exista(nr+p)) nr+=p;
p>>=1;
while (nr+p>Amax) p>>=1;
}
printf("%d.%03d\n",nr/1000,nr%1000);
}
int main()
{
citire();
compute();
freopen("balans.out","w",stdout);
cauta();
fclose(stdout);
return 0;
}