Pagini recente » Cod sursa (job #299237) | Cod sursa (job #1644269) | Cod sursa (job #1412838) | Cod sursa (job #2395112) | Cod sursa (job #1560570)
#include <stdio.h>
#define MAXN 300
int dq[MAXN];
long long s[MAXN], ma[MAXN][MAXN];
inline char bun(int l1, int l2, int c, int x, int m){
int i, st, dr;
st = dr = 0;
s[0] = ma[l2][0] - 1LL * x * (l2 - l1 + 1);
if(l1 != 0)
s[0] -= ma[l1 - 1][0];
if(c == 1 && s[0] > 0)
return 1;
for(i = 1; i < m; i++){
s[i] = ma[l2][i] + s[i - 1] - 1LL * x * (l2 - l1 + 1);
if(l1 != 0)
s[i] -= ma[l1 - 1][i];
if(i >= c - 1 && s[i] >= 0)
return 1;
}
for(i = c; i < m; i++){
if(i - dq[st] + 1 > m)
st++;
while(st < dr && s[i - c] < s[dq[dr - 1]])
dr--;
dq[dr] = i - c;
dr++;
if(st < dr && s[i] - s[dq[st]] >= 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, n2 = n / 2, l1, l2, cs;
for(i = 0; i < n2; i++){
l1 = (n2 + i - 1);
l2 = i + l - 1;
for(j = l2; j < n && j <= l1; j++){
cs = 0;
for(pas = (1 << 26); pas > 0; pas /= 2){
if(bun(i, j, c, cs + pas, m))
cs += pas;
}
if(rez < cs)
rez = cs;
}
}
FILE *out = fopen("balans.out", "w");
fprintf(out, "%.3lf", 1.0 * rez / 1000);
fclose(out);
return 0;
}