Cod sursa(job #1597454)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 februarie 2016 23:42:33
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 300;

bool teren[1 + NMAX][1 + NMAX];
int sum[1 + NMAX];

int main() {
  freopen("teren.in", "r", stdin);
  freopen("teren.out", "w", stdout);
  int n, m, x, sol = 0;

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

  for (int l1 = 1; l1 <= n; ++l1) {
    memset(sum, 0, sizeof(sum));

    for (int l2 = l1; l2 <= n; ++l2) {
      int total = 0, st = 1;

      for (int dr = 1; dr <= m; ++dr) {
        sum[dr] += (int)teren[l2][dr];
        total += sum[dr];

        while(total > x && st <= dr) {
          total -= sum[st];
          ++st;
        }

        sol = max(sol, (l2 - l1 + 1) * (dr - st + 1));
      }
    }
  }

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

  return 0;
}