Pagini recente » Cod sursa (job #702508) | Cod sursa (job #316966) | Cod sursa (job #788846) | Cod sursa (job #868771) | Cod sursa (job #481931)
Cod sursa(job #481931)
#include <stdio.h>
#define NMAX 301
#define ll long long
int n,m,r,c;
int A[NMAX][NMAX],rez;
int deq[NMAX],inc,sf;
ll B[NMAX][NMAX],S2[NMAX],S[NMAX][NMAX],act;
char possible;
void read()
{
scanf("%d%d%d%d",&n,&m,&r,&c);
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
scanf("%d",&A[i][j]);
A[i][j]*=10000;
}
for (j=m+1; j<=2*m; j++)
A[i][j]=A[i][j-m];
}
for (i=n+1; i<=2*n; i++)
for (j=1; j<=2*m; j++)
A[i][j]=A[i-n][j];
}
void actualizare(int i)
{
while (inc!=sf && S2[deq[sf-1]]>=S2[i])
sf--;
deq[sf++]=i;
}
void capat_st(int i)
{
if (i-deq[inc]>m)
inc++;
}
inline int ok(int x)
{
int i,j,k;
possible=0;
for (i=1; i<=2*n; i++)
for (j=1; j<=2*m; j++)
{
B[i][j]=A[i][j]-x;
S[i][j]=S[i-1][j]+B[i][j];
if (S[i][j]>0)
possible=1;
}
if (!possible)
return 0;
for (j=1; j<=2*n; j++)
for (k=j+r-1; k<=2*n && k-j<n; k++)
{
inc=sf=0;
for (i=1; i<=2*m; i++)
{
S2[i]=S2[i-1]+S[k][i]-S[j-1][i];
if (i>=c)
{
actualizare(i-c);
capat_st(i);
act=S2[i]-S2[deq[inc]];
if (act>=0)
return 1;
}
}
}
return 0;
}
inline int cbin()
{
int i,step=(1<<30);
for (i=0; step; step>>=1)
if (ok(i+step))
i+=step;
return i;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
read();
rez=cbin();
printf("%d.%d\n",rez/10000,rez%10000/10);
return 0;
}