Pagini recente » Cod sursa (job #1742045) | Cod sursa (job #960131) | Cod sursa (job #216049) | Cod sursa (job #2854643) | Cod sursa (job #403608)
Cod sursa(job #403608)
#include <stdio.h>
#include <algorithm>
#define MAXN 160
using namespace std;
long long a[MAXN*2][MAXN*2];
long long v[MAXN*2], s[MAXN*2], d[MAXN*2];
int i,j,n,m,r,c, lung;
long long sol,dr;
inline long long calc(long long w)
{
int i;
for (i=1; i<=2*m; i++)
s[i] = s[i-1] + v[i] - w*lung;
int front = 1;
int back = 0;
long long rez = -1;
for (i=c; i< 2*m; i++){
while (back >= front && s[d[back]]>s[i-c]) back--;
d[++back] = i-c;
if (d[front] < i-m) front ++;
rez = max(rez, s[i] - s[d[front]]);
}
return rez;
}
inline void caut(long long st, long long dr)
{
long long mij;
while (st<=dr){
mij = (st+dr)/2;
if (calc(mij)>=0){
sol=mij;
st=mij+1;
}
else
dr=mij-1;
}
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
scanf("%d %d",&n,&m);
scanf("%d %d",&r,&c);
dr=0;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++){
scanf("%Ld",&a[i][j]);
a[i][j]*=1000;
if (a[i][j]>dr) dr=a[i][j];
a[i][j] += a[i-1][j];
a[i][j+m] = a[i][j];
}
for (i=n+1; i<=2*n; i++)
for (j=1; j<=m; j++){
a[i][j] = a[n][j] + a[i-n][j];
a[i][j+m] = a[i][j];
}
for (lung = r; lung<=n; lung++){
memset(v,0,sizeof(v));
for (i=lung; i<n+lung; i++){
for (j=1; j<=2*m; j++)
v[j] =(long long) a[i][j] - a[i-lung][j];
caut(sol,dr);
}
}
long long rez1 = sol/1000;
long long rez2 = sol%1000;
v[1]=v[2]=v[3]=0;
for (j=1; j<=3; j++, rez2/=10)
v[j] = rez2%10;
printf("%Ld.",rez1);
for (j=3; j>=1; j--)
printf("%Ld",v[j]);
printf("\n");
fclose(stdin); fclose(stdout);
return 0;
}