Pagini recente » Cod sursa (job #1378823) | Cod sursa (job #789793) | Cod sursa (job #81515) | Borderou de evaluare (job #1113612) | Cod sursa (job #790335)
Cod sursa(job #790335)
#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<<1],aux[maxdim<<1];
inline long long ssm () {
long long r = -inf;
int n = (m<<1);
for ( int i = m+1 ; i <= n ; ++i ){
S[i] = S[i-m];
}
for ( int i = 1 ; i <= n ; ++i ){
aux[i] = S[i];
aux[i] += aux[i-1];
}
long long scad = inf;
for ( int i = c ; i <= n ; ++i ){
scad = min(scad,aux[i-c]);
r = max(r,aux[i]-scad);
}
return r;
}
inline int 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{
u = m - 1;
}
}
fprintf(g,"%.3lf\n",(double)u/1000);
fclose(f);
fclose(g);
return 0;
}