Cod sursa(job #3188932)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 4 ianuarie 2024 01:47:10
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 400
int sp[NMAX][NMAX], a[NMAX][NMAX];

void calculateDinamics(int n, int m){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            sp[i][j] = sp[i-1][j] + a[i][j];
        }
    }
}

int main(void){
    ofstream cout("teren.out");
    ifstream cin("teren.in");
    int n, m, maxCost, maxim = 0;
    cin >> n >> m >> maxCost;
    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];
        }
    }
    calculateDinamics(n,m);
    for(int i = 1;i<=n;i++){
        for(int j = i;j<=n;j++){
            /// a doua linie
        //    cout << i << " == > " << j << '\n';
            int suma = 0;
            int first = 1;
            for(int last = 1;last <= m; last ++){
                suma += (sp[j][last] - sp[i-1][last]);
             //   cout << suma << '\n';
                while(first <= last && suma > maxCost){
                    suma -= (sp[j][first] - sp[i-1][first]);
                    first++;
                }
                if(first <= last && suma <= maxCost){
                    maxim = max(maxim, (j - i + 1) * (last - first + 1));
                }
            }
        }
    }
    cout << maxim;
}