Cod sursa(job #1743373)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 august 2016 02:24:48
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("teren.in");
ofstream cout("teren.out");

const int MAXN = 300;

int sum[1 + MAXN][1 + MAXN];

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int value;
            cin >> value;
            sum[i][j] = sum[i - 1][j] + value;
        }
    int answer = 0;
    for (int l1 = 1; l1 <= n; l1++)
        for (int l2 = l1; l2 <= n; l2++) {
            int left = 1;
            int total = 0;
            for (int right = 1; right <= m; right++) {
                total = total + sum[l2][right] - sum[l1 - 1][right];
                while(left <= right && total > x) {
                    total = total - (sum[l2][left] - sum[l1 - 1][left]);
                    left++;
                }
                if (total <= x)
                    answer = max(answer, (right - left + 1) * (l2 - l1 + 1));
            }
        }
    cout << answer << "\n";
    return 0;
}