Pagini recente » Cod sursa (job #482949) | Cod sursa (job #445664) | Cod sursa (job #830038) | Cod sursa (job #2036730) | Cod sursa (job #331520)
Cod sursa(job #331520)
#include <stdio.h>
using namespace std;
#define maxn 550
long n, m, i, j, k, r, c, left, right, med, sol, no, mo;
long v[maxn][maxn], s[maxn][maxn];
long coa[maxn], sum[maxn];
long verif(long val)
{
long l1, l2, rez, le, ri;
rez=-2000000000;
for(l1=0; l1<no; l1++)
{
for(l2=l1+r; l2<=n; l2++)
{
for(j=0; j<=m; j++)
{
sum[j]=0;
}
for(j=1; j<=m; j++)
{
sum[j]=sum[j-1]+s[l2][j]-s[l1][j]-val*(l2-l1);
}
coa[1]=0;
le=1;
ri=1;
/* for(j=0; j<=m-c; j++)
{
while(sum[j]<=sum[coa[ri]] && ri>=le)
{
--ri;
}
while(coa[le]<j+c-mo)
{
le++;
}
coa[++ri]=j;
if(rez<sum[j+c]-sum[coa[le]])
{
rez=sum[j+c]-sum[coa[le]];
}
} */
}
}
if(rez>=0) 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);
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d", &v[i][j]);
v[i][j]*=1000;
v[i+n][j]=v[i][j];
v[i+n][j+m]=v[i][j];
v[i][j+m]=v[i][j];
}
}
no=n;
mo=m;
n*=2;
m*=2;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
s[i][j]=s[i-1][j]+v[i][j];
printf("%d ", s[i][j]);
}
printf("\n");
}
left=0;
right=100000000;
while(left<=right)
{
med=(left+right)/2;
if(verif(med))
{
left=med+1;
if(med>sol) sol=med;
}
else
{
right=med-1;
}
}
printf("%d.%03d\n", sol/1000, sol%1000);
}