Cod sursa(job #1174929)

Utilizator dariusdariusMarian Darius dariusdarius Data 24 aprilie 2014 10:53:57
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <algorithm>
#include <fstream>
using namespace std;
const int MAX_N = 305;

int sums[MAX_N][MAX_N];

int main() {
    ifstream fin("teren.in");
    ofstream fout("teren.out");
    int n, m, limit;
    fin >> n >> m >> limit;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            int x;
            fin >> x;
            sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + x;
        }
    }
    int answer = 0;
    for(int i1 = 1; i1 <= n; ++ i1) {
        for(int i2 = i1; i2 <= n; ++ i2) {
            int p1, p2;
            p1 = 1; p2 = 0;
            while(p1 <= m && p2 < m) {
                while(p2 < m && (sums[i2][p2 + 1] - sums[i1 - 1][p2 + 1]) - (sums[i2][p1 - 1] - sums[i1 - 1][p1 - 1]) <= limit) {
                    ++ p2;
                }
                answer = max(answer, (i2 - i1 + 1) * (p2 - p1 + 1));
                ++ p1;
                p2 = max(p2, p1 - 1);
            }
        }
    }
    fout << answer << "\n";
    return 0;
}