Cod sursa(job #2958859)

Utilizator gripzStroescu Matei Alexandru gripz Data 28 decembrie 2022 17:46:16
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#pragma GCC optimize("Ofast")

#define MAXN 303

using namespace std;

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

int N, M, X, m[MAXN][MAXN], S[MAXN][MAXN], sol;

int main()
{
    fin >> N >> M >> X;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            fin >> m[i][j];
        }
    }

    // construire sume partiale
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            S[i][j] = S[i][j - 1] + m[i][j];
        }
    }

    for(int i = 1; i <= M; i++) {
        for(int j = i; j <= M; j++) {
            int s = 0;
            int up = 1;
            for(int l = 1; l <= N; l++) {
                s = s + S[l][j] - S[l][j - i];
                while(s > X) {
                    s  = s - (S[up][j] - S[up][j - i]);
                    up++;
                }

                if(i * (l - up + 1) > sol) {
                    sol = i * (l - up + 1);
                }
            }
        }
    }

    fout << sol;

    /*for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            fout << s[i][j] << " ";
        }
        fout << endl;
    }*/

    return 0;
}