Cod sursa(job #2875701)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 22 martie 2022 10:26:06
Problema Teren Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
#define MAXN 300

using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");

void citire(int &n, int &m, int &x, int mat[][MAXN]) {
    fin >> n >> m >> x;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++)
            fin >> mat[i][j];
}

int rezolvare(int n, int m, int x, int mat[][MAXN]) {
    for (int j = 0; j < m; j++) //sume partiale pe verticala
        for (int i = 2; i <= n; i++)
            mat[i][j] += mat[i - 1][j];
    int maxi = 0;
    for (int j = n; j >= 1; j--) {
        for (int i = 1; i <= j; i++) {
            int a[MAXN], st = 0, dr = 0, sum = 0;
            for (int k = 0; k < m; k++)
                a[k] = mat[j][k] - mat[i - 1][k];

            while (dr < m) {
                sum += a[sum];
                while (st <= dr && sum > x)
                    sum -= a[st], st++;
                int arie = (dr - st) * (j - i) + 1;
                if (st <= dr && arie > maxi)
                    maxi = arie;
                dr++;
            }
        }
    }

    return maxi;
}

int main() {
    int n, m, x, mat[MAXN + 1][MAXN];
    citire(n, m, x, mat);
    fout << rezolvare(n, m, x, mat);
    return 0;
}