Pagini recente » Cod sursa (job #2522319) | Cod sursa (job #47116) | Cod sursa (job #1631167) | Cod sursa (job #507266) | Cod sursa (job #790355)
Cod sursa(job #790355)
#include<stdio.h>
#include<algorithm>
#define maxdim 153
using namespace std;
FILE*f=fopen("balans.in","r");
FILE*g=fopen("balans.out","w");
const long long inf = 1LL<<62;
int n,m,l,c;
int A[maxdim][maxdim];
long long S[maxdim],aux[maxdim],deque[maxdim];
inline long long ssm () {
long long r = -inf,total = 0;
for ( int i = 1 ; i <= m ; ++i ){
aux[i] = S[i];
aux[i] += aux[i-1];
total += S[i];
}
long long scad = inf;
for ( int i = c ; i <= m ; ++i ){
scad = min(scad,aux[i-c]);
r = max(r,aux[i]-scad);
}
int front = 1,back = 0,lung = m-c;
for ( int i = 1 ; i <= m ; ++i ){
while ( front <= back && aux[ deque[back] ] < aux[i] ){
deque[back--] = 0;
}
deque[++back] = i;
if ( deque[front] < i-lung ){
++front;
}
r = max(r,total-aux[i]+aux[deque[front]]);
}
return r;
}
inline long long get_max ( int medie ){
long long r = -inf;
for ( int jos = 1 ; jos <= n ; ++jos ){
int nrl = 1,up = jos;
for ( int i = 1 ; i <= m ; ++i ){
S[i] = A[jos][i] - medie;
}
do{
if ( nrl >= l ){
r = max(r,ssm());
}
++nrl; --up; if ( !up ) up = n;
for ( int i = 1 ; i <= m ; ++i ){
S[i] += A[up][i] - medie;
}
}while ( up != jos );
}
return r;
}
int main () {
fscanf(f,"%d %d %d %d",&n,&m,&l,&c);
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= m ; ++j ){
fscanf(f,"%d",&A[i][j]);
A[i][j] *= 1000;
}
}
int p = 0,m,u = 100000000;
while ( p <= u ){
m = (p + u) >> 1;
if ( get_max(m) >= 0 ){
p = m + 1;
}
else{
//printf("%d\n",u);
u = m - 1;
}
}
fprintf(g,"%.3lf\n",(double)u/1000);
fclose(f);
fclose(g);
return 0;
}