Pagini recente » Cod sursa (job #1912458) | Cod sursa (job #2643817) | Cod sursa (job #2917471) | Cod sursa (job #2131701) | Cod sursa (job #404173)
Cod sursa(job #404173)
#include <stdio.h>
#include <algorithm>
#define MAXN 512
using namespace std;
long long a[MAXN][MAXN];
long long v[MAXN], s[MAXN], d[MAXN];
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++){
for (; back >= front && s[d[back]]>s[i-c]; back--);
d[++back] = i-c;
if (d[front] < i-m) front ++;
if (rez < s[i] - s[d[front]])
rez = s[i] - s[d[front]];
rez = max(rez, s[i] - s[d[front]]);
}
return rez;
}
inline bool calc2(long long w)
{
for (lung = r; lung<=n; lung++)
for (i=lung; i<n+lung; i++){
for (j=1; j<=2*m; j++)
v[j] =a[i][j] - a[i-lung][j];
if (calc(w)>=0) return true;
}
return false;
}
inline void caut(long long st, long long dr)
{
long long mij;
while (st<=dr){
mij = (st+dr)/2;
if (calc2(mij)){
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++){
for (i=lung; i<n+lung; i++){
for (j=1; j<=2*m; j++)
v[j] =a[i][j] - a[i-lung][j];
}
}
caut(0,dr);
printf("%Ld.",sol/1000);
sol%=1000;
if (sol>=100) printf("%Ld",sol);
else
if (sol>=10) printf("0%Ld",sol);
else printf("00%Ld",sol);
printf("\n");
fclose(stdin); fclose(stdout);
return 0;
}