Pagini recente » Cod sursa (job #2879382) | Cod sursa (job #1018692) | Cod sursa (job #2863907) | Cod sursa (job #569977) | Cod sursa (job #541147)
Cod sursa(job #541147)
#include <cstdio>
#include <cmath>
#define nmax 310
#define X 1000
int st, dr, sol;
int a[nmax][nmax], n, m, r, c, p[nmax];
long long b[nmax][nmax], s[nmax][nmax], v[nmax], q[nmax];
int verif(int x)
{
int i, j, st, dr, y, i1, i2;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) b[i][j]=a[i][j]*X-x;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
s[i][j]=s[i-1][j]+b[i][j];
for (i1=1; i1<=n; i1++)
for (i2=i1+r-1; i2<=n && i1+n/2>i2; i2++)
{
for (j=1; j<=m; j++) v[j]=v[j-1]+s[i2][j]-s[i1-1][j];
st=1;
dr=0;
if (v[c]>=0) return 1;
y=c+1;
for (j=1; y<=m; j++, y++)
{
while (v[j]<q[dr] && st<=dr) dr--;
while (p[st]+m/2<=y && st<=dr) st++;
dr++;
q[dr]=v[j];
p[dr]=j;
if (v[y]>=q[st]) return 1;
}
}
return 0;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
scanf("%d %d %d %d",&n, &m, &r, &c);
int i, j, mij;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) scanf("%d",&a[i][j]);
st=1<<30;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
if (a[i][j]<st) st=a[i][j];
if (a[i][j]>dr) dr=a[i][j];
}
n*=2;
m*=2;
st*=X;
dr*=X;
while (st<=dr)
{
mij=(st+dr)/2;
if (verif(mij))
{
st=mij+1;
sol=mij;
} else dr=mij-1;
}
i=sol%X;
printf("%d.",sol/X);
if (i<10) printf("00"); else
if (i<100) printf("0");
printf("%d\n",i);
}