Pagini recente » Cod sursa (job #36053) | Cod sursa (job #2258442) | Cod sursa (job #1623715) | Cod sursa (job #982655) | Cod sursa (job #331736)
Cod sursa(job #331736)
#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], Min;
long long Sum, S[Nmax][Nmax], v[Nmax], INF;
int cont ( int X ){
int p, u;
long long Sum = - INF;
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);
v[l]+= v[l-1];
}
p = u = 1; Min = 0;
for(l = 1; l + c <= M && l <= M; l++){
if(Min > v[l]) Min = v[l];
if(Sum < v[l + c ] - Min ) Sum = v[l + c ] - Min;
}
}
}
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; INF = 1 << 30; INF*= 2000;
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;
}