Cod sursa(job #2676540)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 24 noiembrie 2020 16:07:39
Problema Teren Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("teren.in");
ofstream fout("teren.out");
int n, m, rez, x, mt[105][105];

void readInput() {
    fin >> n >> m >> x;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> mt[i][j];
            mt[i][j] += mt[i - 1][j] + mt[i][j - 1] - mt[i - 1][j - 1];
        }
    }
    return;
}

void solve() {
    for (int i1 = 1; i1 <= n; ++i1) {
        for (int i2 = i1; i2 <= n; ++i2) {
            vector <int> v;
            for (int j = 1; j <= m; ++j)
                v.push_back(mt[i2][j] - mt[i2][j - 1] - mt[i1 - 1][j] + mt[i1 - 1][j - 1]);
            int maxim = 0;
            for (int st = 0, dr = 0, sum = v[0]; dr < m;) {
                if (sum <= x || st == dr) {
                    ++dr;
                    if (dr < m)
                        sum += v[dr];
                }
                else {
                    sum -= v[st];
                    ++st;
                }
                if (sum <= x && dr < m)
                    maxim = max(maxim, dr - st + 1);
            }
            rez = max(rez, maxim * (i2 - i1 + 1));
        }
    }
    return;
}

int main() {
    readInput();
    solve();
    fout << rez;
    return 0;
}