Cod sursa(job #2037877)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 12 octombrie 2017 21:53:06
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>

const int MAXN = 3e2;

int s[MAXN + 1][MAXN + 1];

inline int max(int a, int b) {
  return a > b ? a : b;
}

int main() {
  int n, m, k, x, sum, st, ans;
  FILE *f = fopen("teren.in", "r");
  fscanf(f, "%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      fscanf(f, "%d", &x);
      s[i][j] = s[i - 1][j] + x;
    }
  }
  fclose(f);
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      sum = 0;
      st = 1;
      for (int dr = 1; dr <= m; ++dr) {
        sum += s[j][dr] - s[i - 1][dr];
        while (st <= dr && k < sum) {
          sum -= s[j][st] - s[i - 1][st];
          ++st;
        }
        if (sum <= k) {
          ans = max(ans, (j - i + 1) * (dr - st + 1));
        }
      }
    }
  }
  f = fopen("teren.out", "w");
  fprintf(f, "%d\n", ans);
  fclose(f);
  return 0;
}