Pagini recente » Cod sursa (job #2312580) | Cod sursa (job #896105) | Cod sursa (job #638796) | Cod sursa (job #3240826) | Cod sursa (job #331726)
Cod sursa(job #331726)
#include <cstdio>
#define Nmax 310
int n, m, r, c, N, i, j, p, u, mij, sol, MAX, M, l;
int a[Nmax][Nmax], d[Nmax];
long long Sum, S[Nmax][Nmax], v[Nmax];
int cont ( int X ){
int p, u;
long long Sum = - 1<<30; Sum*= 2000;
for (i = 1; i <= N; i++){
j = i + r - 1; if( j > N) break;
for(; j <= N; j++){
for(l = 1; l <= M; l++)
v[l] = S[j][l] - S[i-1][l] - (long long)X * (long long)(j - i + 1);
p = u = 1; d[1] = 1;
for(l = 1; l <= M; l++){
while( p <= u && l - d[p] >= c ) p++;
while( p <= u && v[ d[u] ] <= v[l] ) u--;
d[++u] = l;
if(l >= c && Sum < v[ d[p] ]) Sum = v[ d[p] ];
}
}
}
if( Sum >= 0 ) return 1;
return 0;
}
int main (){
FILE *f = fopen("balans.in", "r");
FILE *g = fopen("balans.out", "w");
fscanf(f,"%d %d %d %d", &n, &m, &r, &c);
for (i = 1; i <= n; i++)
for(j = 1; j <= m; j++){
fscanf(f,"%d", &a[i][j]); a[i][j]*= 1000;
if(MAX < a[i][j]) MAX = a[i][j];
}
N = n << 1; M = m << 1;
for (i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
a[i][j+m] = a[i][j];
for (i = 1; i <= n; i++)
for(j = 1; j <= M; j++)
a[i+n][j] = a[i][j];
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
S[i][j] = S[i-1][j] + (long long)a[i][j];
p = 0; u = MAX;
while(p <= u){
mij = (p + u) >> 1;
if( cont(mij) ){
sol = mij;
p = mij + 1;
}
else
u = mij - 1;
}
fprintf(g,"%.3lf", (double)((double)sol / (double)1000) );
fclose(f);
fclose(g);
return 0;
}