Cod sursa(job #1597376)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 februarie 2016 22:10:57
Problema Teren Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int NMAX = 300;

bool teren[1 + NMAX][1 + NMAX];
int sum[1 + NMAX][1 + NMAX];
int x, sol = 0;

queue <int> q;

int numar(int l1, int c1, int l2, int c2) {
  if (l1 > l2 || c1 > c2)
    return 0;
  return sum[l2][c2] - sum[l1 - 1][c2] - sum[l2][c1 - 1] + sum[l1 - 1][c1 - 1];
}

bool verific(int l1, int c1, int l2, int c2) {
  int nrI = numar(l1 + 1, c1 + 1, l2 - 1, c2 - 1);
  int nrL = numar(l1, c1, l2, c2) - nrI;

  return nrI <= x && nrL == 0;
}

int main() {
  freopen("teren.in", "r", stdin);
  freopen("teren.out", "w", stdout);
  int n, m, tip;

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

  for (int l1 = 1; l1 <= n; ++l1) {
    for (int l2 = l1; l2 <= n; ++l2) {
      while(!q.empty())
        q.pop();

      for (int j = 1; j <= m; ++j) {
        if (numar(l1, j, l2, j) == 0) {
          q.push(j);
          while (!q.empty() && !verific(l1, q.front(), l2, j))
            q.pop();

          sol = max(sol, (l2 - l1 + 1) * (j - q.front() + 1));
        }
      }
    }
  }

  printf("%d\n", sol);

  return 0;
}