Cod sursa(job #2455830)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 12 septembrie 2019 20:34:22
Problema Balans Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <iomanip>
#include <cstdio>

using namespace std;

const int N = 300 + 7;
int n, m, x, y;
int a[N][N];
double b[N][N];
double c[N], d[N];
double mn[N];

bool ok(double val) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      b[i][j] = a[i][j] - val;
    }
  }
  for (int l = 1; l <= m; l++) {
    for (int i = 1; i <= n; i++) {
      c[i] = 0;
    }
    for (int r = l + y - 1; r <= m; r++) {
      for (int i = 1; i <= n; i++) {
        c[i] += b[i][r];
        d[i] = d[i - 1] + c[i];
        mn[i] = min(mn[i - 1], d[i]);
        if (i - x >= 0 && d[i] - mn[i - x] >= 0) {
          return 1;
        }
      }
      /// d[i] - d[j] cu i - j >= x =======> i - x >= j
    }
  }
  return 0;
}

int main() {
  freopen ("balans.in", "r", stdin);
  freopen ("balans.out", "w", stdout);

  scanf("%d %d %d %d", &n, &m, &x, &y);

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
    }
  }

  n *= 2;
  m *= 2;

  double l = 0, r = 100000;
  for (int i = 1; i <= 50; i++) {
    double md = (l + r) * 0.5;
    if (ok(md)) {
      l = md;
    } else {
      r = md;
    }
  }
  cout << fixed << setprecision(6) << l << '\n';


  return 0;
}