Cod sursa(job #2768723)

Utilizator DragosC1Dragos DragosC1 Data 11 august 2021 23:05:41
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
using namespace std;

int n, m, K;
int a[301][301];

void read() {
    int i, j;
    ifstream f("teren.in");
    f >> n >> m >> K;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            f >> a[i][j];
    f.close();
}

int Max;
int L[301][301];

void solve() {
    int i, j, k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            L[i][j] = L[i - 1][j] + a[i][j];
            
    int L1, L2, st, sum;
    for (L1 = 1; L1 <= n; L1++) 
        for (L2 = L1; L2 <= n; L2++) {
            st = 1, sum = 0;
            for (k = 1; k <= m; k++) {
                sum += L[L2][k] - L[L1 - 1][k];
                while (sum > K) {
                    sum -= L[L2][st] - L[L1 - 1][st];
                    st++;
                }
                if ((k - st + 1) * (L2 - L1 + 1) > Max)
                    Max = (k - st + 1) * (L2 - L1 + 1);
            }
        }
}

void output() {
    ofstream g("teren.out");
    g << Max;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}