Pagini recente » Cod sursa (job #724226) | Cod sursa (job #2543153) | Cod sursa (job #2438528) | Cod sursa (job #1810247) | Cod sursa (job #332083)
Cod sursa(job #332083)
#include <cstdio>
#define Nmax 302
int i, n, r, l, m, N, M, Vmax, p, u, mij, sol, j, c, Vmin;
int a[Nmax][Nmax], d[Nmax];
long long INF, Sum, v[Nmax], S[Nmax][Nmax], Q;
int cont(int X){
int p, u;
Sum = - INF;
for (i = 1; i <= n; i++)
for (j = i + r - 1; j - i + 1 <= n; j++) {
Q = (long long)X * (long long)(j - i + 1);
for (l = 1; l <= M; l++) {
v[l] = S[j][l] - S[i-1][l] - Q;
v[l]+= v[l-1];
}
p = u = 1; d[1] = 1;
for (l = 2; l + c <= M; l++) {
while ( p <= u && l - d[p] >= m - c + 1 ) p++;
while ( p <= u && v[l] <= v[ d[u] ] ) u--;
d[++u] = l;
if( Sum < v[l + c] - v[ d[p] ] ) Sum = v[l + c] - 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); Vmin = 100000001;
for (i = 1; i <= n; i++)
for(j = 1; j <= m; j++){
fscanf(f,"%d", &a[i][j]);
a[i][j]*= 1000;
if(a[i][j] > Vmax) Vmax = a[i][j];
if(a[i][j] < Vmin ) Vmin = 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 = Vmin; u = Vmax; INF = 1 << 30; INF*= 1000;
while ( p <= u ) {
mij = (p + u) >> 1;
if (cont(mij)){
sol = mij;
p = mij + 1;
}
else
u = mij - 1;
}
fprintf (g,"%.3lf", (double)sol / (double)1000);
fclose (f);
fclose (g);
return 0;
}