Cod sursa(job #2332771)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 31 ianuarie 2019 11:12:02
Problema Balans Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;

const int NMAX = 305;

int n, m, r, c;
ld v[NMAX];
ll val[NMAX];
ll a[NMAX][NMAX];
ll sum_col[NMAX][NMAX];

template <class T>
void maxi (T &a, T b) {
  a = max (a, b);
}

bool check (ll x) {
  for (int i = 1; i <= 2 * m; ++i) {
    v[i] = val[i] - x;
    v[i] += v[i - 1];
  }

  deque <ll> dq;
  for (int i = c; i <= 2 * m; ++i) {
    while (!dq.empty() && i - dq.front() > m) {
      dq.pop_front();
    }
    if (i >= c) {
      while (!dq.empty() && v[dq.back()] >= v[i - c]) {
        dq.pop_back();
      }
      dq.pb (i - c);
      if (v[i] - v[dq.front()] >= 0) {
        return true;
      }
    }
  }

  return false;
}

ll binSearch (int dist) {
  ll lo = 1, hi = 1e8;
  while (lo != hi) {
    ll mid = lo + (hi - lo + 1) / 2;
    if (check (mid * dist)) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  return lo;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

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

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

  for (int i = 1; i <= 2 * n; ++i) {
    for (int j = 1; j <= 2 * m; ++j) {
      sum_col[i][j] = sum_col[i - 1][j] + a[i][j];
    }
  }

  ll ans = 0;
  for (int l1 = 1; l1 <= 2 * n - r + 1; ++l1) {
    int lim = min (l1 + n - 1, 2 * n);
    for (int l2 = l1 + r - 1; l2 <= lim; ++l2) {
      for (int i = 1; i <= 2 * m; ++i) {
        val[i] = sum_col[l2][i] - sum_col[l1 - 1][i];
      }
      maxi (ans, binSearch (l2 - l1 + 1));
    }
  }

  printf ("%.3f\n", ans / 1000.0);

  fclose (stdin);
  fclose (stdout);

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}