Pagini recente » Cod sursa (job #1433532) | Istoria paginii runda/18_07_12 | Istoria paginii runda/oni_2017_cl10_ziua2_ | Cod sursa (job #2471030) | Cod sursa (job #1560525)
#include <stdio.h>
#define MAXN 300
#define EPS 0.0000001
#define INF 9000000000000000000.0
int ma[MAXN][MAXN], dq[MAXN];
long long s[MAXN], sum[MAXN];
inline double min2(double a, double b){
return a < b ? a : b;
}
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; j < n && j <= l1; j++){
for(k = 0; k < m; k++)
sum[k] += ma[j][k];
if(j >= l2){
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, "%d", &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;
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;
}