Cod sursa(job #1466575)

Utilizator akaprosAna Kapros akapros Data 29 iulie 2015 15:29:08
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Nmax 302
using namespace std;
int n, m, x, i, j, a[Nmax][Nmax], 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[i][j]);

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