Pagini recente » Cod sursa (job #2848261) | Cod sursa (job #1714807) | Cod sursa (job #221315) | Cod sursa (job #2942843) | Cod sursa (job #331674)
Cod sursa(job #331674)
#include <cstdio>
#define Nmax 310
int n, m, r, c, N, i, j, p, u, mij, sol, MAX, M, l;
int a[Nmax][Nmax], v[Nmax], d[Nmax], S[Nmax][Nmax];
int cont ( int X ){
int Sum = - 1<<30, p, u;
for (i = 1; i <= N; i++){
for(j = i + r - 1; j <= N; j++){
for(l = 1; l <= M; l++)
v[l] = S[j][l] - S[i-1][l] - X * (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] = i;
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] + a[i][j];
p = 0; u = MAX * 1000;
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;
}