Cod sursa(job #2154437)

Utilizator NeredesinI am not real Neredesin Data 6 martie 2018 22:43:44
Problema Balans Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream in("balans.in");
ofstream out("balans.out");

typedef long long ll;

const int NMAX = 150;
const int NORM = 1e3;

int n, m, r, c;
ll res;
ll sum[1 + 2 * NMAX];
ll a[1 + 2 * NMAX][1 + 2 * NMAX];
ll sp[1 + 2 * NMAX][1 + 2 * NMAX];
ll maxx;

deque < int > dq;

bool ok(int x) {
  fill(sum, sum + 2 * NMAX + 1, 0);

  for(int l1 = 1; l1 <= n; l1++) {
    for(int l2 = l1 + r - 1; l2 <= n; l2++) {
      dq.clear();

      for(int j = 1; j <= m; j++)
        sum[j] = sum[j - 1] + sp[l2][j] - sp[l1 - 1][j] - (l2 - l1 + 1) * x;

      for(int i = c; i <= m; i++) {
        while(!dq.empty() && sum[i - c] <= sum[dq.back()])
          dq.pop_back();
        dq.push_back(i - c);

        if(0 <= sum[i] - sum[dq.front()])
          return true;
      }
    }
  }

  return false;
}

int main()
{
  in >> n >> m >> r >> c;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      in >> a[i][j];
      a[i][j] *= NORM;
      maxx = max(maxx, a[i][j]);
    }
  }

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];

  n *= 2;
  m *= 2;

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      sp[i][j] = sp[i - 1][j] + a[i][j];

  int from = 0, to = maxx;
  while(from <= to) {
    ll mid = (from + to) / 2;
    if(ok(mid) == true) {
      res = mid;
      from = mid + 1;
    } else
      to = mid - 1;
  }

  out << res / NORM << '.' << res % NORM << '\n';

  in.close();
  out.close();
  return 0;
}