Cod sursa(job #2153918)

Utilizator tomadimitrieDimitrie-Toma Furdui tomadimitrie Data 6 martie 2018 16:11:45
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>

/*
 3 5 1
 0 0 0 0 1
 0 1 0 0 0
 0 0 0 1 0
 */

int main(int argc, const char * argv[]) {
    std::ifstream f("teren.in");
    std::ofstream g("teren.out");
    int N, M, X;
    f >> N >> M >> X;
    int S[301][301] = { 0 };
    int a[301][301];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            f >> a[i][j];
            if (i == 1 && j == 1) {
                S[i][j] = a[i][j];
            } else if (i == 1) {
                S[i][j] = a[i][j] + S[i][j - 1];
            } else if (j == 1) {
                S[i][j] = a[i][j] + S[i - 1][j];
            } else {
                S[i][j] = a[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
            }
        }
    }
    int Amax = 0;
    for (int l1 = 1; l1 <= N; l1++) {
        for (int l2 = l1; l2 <= N; l2++) {
            int A[301];
            for (int j = 1; j <= M; j++) {
                A[j] = S[l2][j] - S[l2][j - 1] - S[l1 - 1][j] + S[l1 - 1][j - 1];
            }
            int i = 1, s = 0;
            for (int j = 1; j <= M; j++) {
                s += A[j];
                while (i <= j && s > X) {
                    s -= A[i];
                    i++;
                }
                if (i <= j) {
                    Amax = std::max(Amax, (j - i + 1) * (l2 - l1 + 1));
                }
            }
        }
    }
    g << Amax;
    return 0;
}