Cod sursa(job #1308539)

Utilizator diana97Diana Ghinea diana97 Data 4 ianuarie 2015 12:50:49
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("teren.in");
ofstream g ("teren.out");

const int NMAX = 300 + 1;

int n, m, x;
int v[NMAX][NMAX];

void citeste() {
    f >> n >> m >> x;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f >> v[i][j];
            v[i][j] += v[i - 1][j];
        }
}

void rezolva() {
    int maxim = -1;
    for (int l1 = 1; l1 <= n; l1++)
        for (int l2 = l1; l2 <= n; l2++) {
            int c2 = 1, c1 = 1, s = 0;
            while(c2 <= m) {
                s += v[l2][c2] - v[l1 - 1][c2];
                while(s > x) {
                    c1++;
                    s = s - (v[l2][c1 - 1] - v[l1 - 1][c1 - 1]);
                }
                int rez = (c2 - c1 + 1) * (l2 - l1 + 1);
                c2++;
                maxim = max(rez, maxim);
            }
        }
    g << maxim << '\n';
}

int main() {
    citeste();
    rezolva();
}