Cod sursa(job #1689516)

Utilizator akaprosAna Kapros akapros Data 14 aprilie 2016 12:24:30
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
#define maxN 302
using namespace std;
int n, m, sp[maxN][maxN], X, ans;
void read()
{
    int i, j;
    freopen("teren.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &X);
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
        {
            int a;
            scanf("%d", &a);
            sp[j][i] = sp[j][i - 1] + a;
        }
}
void solve()
{
    int i, j, x;
    for (i = 1; i <= n; ++ i)
        for (j = i; j <= n; ++ j)
    {
        int p = 1, sum = 0, ok = 0;
        for (x = 1; x <= m; ++ x)
        {
            sum += sp[x][j] - sp[x][i - 1];
            while (sum > X && p <= x)
            {
                sum  -= (sp[p][j] - sp[p][i - 1]);
                ++ p;
            }

            if (p <= x)
                ok = 1;
            if ((j - i + 1) * (x - p + 1) > ans)
                ans = (j - i + 1) * (x - p + 1);
        }
        if (!ok)
            break;
    }
}
void write()
{
    freopen("teren.out", "w", stdout);
    printf("%d", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}