Cod sursa(job #2530448)

Utilizator AlexNeaguAlexandru AlexNeagu Data 24 ianuarie 2020 19:55:12
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
ifstream in("teren.in");
ofstream out("teren.out");
int n, m, k, max_area = 0;
int t[N][N];
int main() {
  in >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int x;
      in >> x;
      t[i][j] = t[i - 1][j] + x;
    }
  }
  for (int i = 1; i <= n; i++) { // set upp line
    for (int j = i; j <= n; j++) { // set low line
      int st = 1, dr = 1, s = 0;
      while (st <= m && dr <= m) {
          if (t[j][dr] - t[i - 1][dr] + s <= k) {
            s += t[j][dr] - t[i - 1][dr];
            max_area = max(max_area, (dr - st + 1) * (j - i + 1));
            dr++;
          }
          else {
            while(t[j][dr] - t[i - 1][dr] + s > k && st < dr) {
              s -= t[j][st] - t[i - 1][st];
              st++;
            }
            if (t[j][dr] - t[i  - 1][dr] + s <= k) {
              s += t[j][dr] - t[i - 1][dr];
              max_area = max(max_area, (dr - st + 1) * (j - i + 1));
              dr++;
            }
            else {
              st++;
              dr++;
          }
        }
      }
    }
  }
  out << max_area << "\n";
}