Cod sursa(job #3193851)

Utilizator philippePhilippe Colta philippe Data 15 ianuarie 2024 21:14:22
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
using namespace std;
ifstream cin("teren.in");
ofstream cout("teren.out");
int a[305][305], sp[305][305];

int main() {
  int n, m, x, ans = 0;
  cin >> n >> m >> x;
  for(int i = 1 ; i <= n; i++)
    for(int j = 1; j <= m; j++) {
      cin >> a[i][j];
      sp[i][j] = sp[i - 1][j] + a[i][j]; // Sume partiale pe linii
    }

  for(int i = 1; i <= n; i++) {
    for(int j = i; j <= n; j++) {
      // Prin aceste doua for-uri de mai sus mi-am fixat liniile in care voi lucra

      // Acum problema seamana foarte mult cu problema pe 1D
      int st = 1, dr = 1, s = 0;
      while(dr <= m) {
        s += sp[j][dr] - sp[i - 1][dr];
        while(s > x) {
          s -= sp[j][st] - sp[i - 1][st];
          st++;
        }

        ans = max(ans, (j - i + 1) * (dr - st + 1));
        dr++;
      }
    }
  }

  cout << ans << '\n';

  return 0;
}