Pagini recente » Cod sursa (job #972826) | Cod sursa (job #3247791) | Cod sursa (job #534550) | Cod sursa (job #1932324) | Cod sursa (job #1560531)
#include <stdio.h>
#define MAXN 300
int dq[MAXN];
long long s[MAXN], sum[MAXN], ma[MAXN][MAXN];
inline char bun(int n, int m, int l, int c, int x){
int i, j, k, st, dr, l1, l2, n2 = (n / 2), m2 = (m / 2);
for(i = 0; i < (n >> 1); i++){
for(j = 0; j < m; j++)
sum[j] = 0;
l1 = (n2 + i - 1);
l2 = i + l - 1;
for(j = i + l - 1; j < n && j <= l1; j++){
for(k = 0; k < m; k++){
sum[k] = ma[j][k];
if(i != 0)
sum[k] -= ma[i - 1][k];
}
st = dr = 0;
s[0] = sum[0] - 1LL * (j - i + 1) * x;
for(k = 1; k < m; k++){
s[k] = s[k - 1] + sum[k] - 1LL * (j - i + 1) * x;
if(st < dr && k - dq[st] + 1 > n / 2)
st++;
if(k >= c){
while(st < dr && s[k - c] < s[dq[dr - 1]])
dr--;
dq[dr] = k - c;
dr++;
}
if(st < dr && s[k] - s[dq[st]] >= 0)
return 1;
}
for(k = c - 1; k < m2; k++)
if(s[k] >= 0)
return 1;
}
}
return 0;
}
int main(){
FILE *in = fopen("balans.in", "r");
int n, m, l, c, i, j;
fscanf(in, "%d%d%d%d", &n, &m, &l, &c);
if(l == 0)
l++;
if(c == 0)
c++;
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
fscanf(in, "%lld", &ma[i][j]);
ma[i][j] *= 1000;
ma[i + n][j] = ma[i][j + m] = ma[i + n][j + m] = ma[i][j];
}
}
n *= 2; m *= 2;
for(i = 1; i < n; i++)
for(j = 0; j < m; j++)
ma[i][j] += ma[i - 1][j];
int rez = 0, pas;
for(pas = (double)(1 << 26); pas > 0; pas /= 2){
if(bun(n, m, l, c, rez + pas))
rez += pas;
}
FILE *out = fopen("balans.out", "w");
fprintf(out, "%.3lf", 1.0 * rez / 1000);
fclose(out);
return 0;
}