Cod sursa(job #3221780)

Utilizator deerMohanu Dominic deer Data 8 aprilie 2024 02:15:56
Problema Teren Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define YES { fout << "DA" << endl; return; }
#define NO { fout << "NU" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 3e2;
using namespace std;
ifstream fin ("teren.in");
ofstream fout ("teren.out");
int16_t spcol[NMAX + 5][NMAX + 5], arr[NMAX + 5];
int n, m, ans = INT_MIN, x;
signed main() {
    fin >> n >> m >> x;
    for (int i = 1; i <= n; i++)
        for (int j = 1, a; j <= m; j++)
            fin >> a, spcol[i][j] = spcol[i - 1][j] + a;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int k = 1; k <= m; ++k)
                arr[k] = spcol[j][k] - spcol[i - 1][k];
            int left = 1, right = 1, sum = arr[1];
            while (right <= n - 1) {
                if (sum + arr[right + 1] <= x) {
                    sum += arr[++right];
                    ans = max(ans, (j - i + 1) * (right - i + 1));
                } else
                    sum -= arr[left++];
            }
        }
    }
    fout << ans;
    return 0;
}