Cod sursa(job #2154511)

Utilizator NeredesinI am not real Neredesin Data 6 martie 2018 23:42:23
Problema Balans Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <deque>

using namespace std;

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

typedef long long ll;

const ll NMAX = 160;

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


bool ok(ll x) {
  ll mx;

  for(int l1 = 1; l1 <= n; l1++) {
    for(int l2 = l1 + r - 1; l2 <= l1 + n - 1; l2++) {
      for(int i = 1; i <= 2 * m; i++)
        sum[i] = sum[i - 1] + sp[l2][i] - sp[l1 - 1][i] - (l2 - l1 + 1) * x;

      mx = sum[c];
      dq[1] = 1;
      p = 1;
      u = 0;

      for(int i = c + 1; i <= 2 * m; i++) {
        while(p <= u && dq[p] + m - 1 < i)
          p++;

        while(p <= u && sum[i] - sum[dq[u] - 1] <= sum[i] - sum[i - c])
          u--;
        dq[++u] = i - c + 1;
        mx = max(mx, sum[i] - sum[dq[p] - 1]);
        if(m < dq[p])
          break;
      }

      if(0 <= mx)
        return true;
    }
  }

  return false;
}

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

  //in >> n >> m >> r >> c;
  scanf("%d%d%d%d", &n, &m, &r, &c);

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      //in >> a[i][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];
      maxx = max(maxx, 1LL * a[i][j]);
    }
  }

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

  ll from = 0;
  ll to = maxx;

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

  //out << setprecision(3) << fixed;
  //out << res * 1.0 / 1000 << '\n';

  printf("%ld.", res / 1000);
  printf("%ld", res % 1000);
  //in.close();
  //out.close();
  fclose(stdin);
  fclose(stdout);
  return 0;
}