Cod sursa(job #1466570)

Utilizator akaprosAna Kapros akapros Data 29 iulie 2015 15:26:00
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Nmax 302
using namespace std;
int n, m, x, i, j, a, s[Nmax][Nmax];
int sol;
void read()
{
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &x);
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
        {
            scanf("%d", &a);
            s[i][j] = s[i - 1][j] + a;
        }

}
void solve()
{
    int sum, l, k;
    for (i = 1; i <= n; ++ i)
        for (j = i; j <= n; ++ j)
        {
            k = 1;
            sum = s[j][1] - s[i - 1][1];
            for (l = 2; l <= m; ++ l)
            {
                sum += s[j][l] - s[i - 1][l];
                while (sum > x && k <= l)
                    sum = sum - (s[j][k] + s[i - 1][k]),
                    ++ k;
                sol = max(sol, (l - k + 1) * (j - i + 1));
            }
        }
}
void write()
{
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}