Cod sursa(job #1593637)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 8 februarie 2016 19:25:17
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
#define nmax 305

using namespace std;

int mx,n,m,k,a[nmax][nmax],s[nmax][nmax],v[nmax];

inline void Input()
{
    int i,j;
    ifstream fin("teren.in");
    fin>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
    fin.close();
}

inline void Create()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+a[i][j];
}

inline void MaxSurface(int st,int dr)
{
    int i;
    int sum=0,x=1;
    for(i=1;i<=m;i++)
    {
        sum+=v[i];
        while(x<i&&sum>k)
            sum-=v[x++];
        if(x<i&&(dr-st+1)*(i-x+1)>mx)
            mx=(dr-st+1)*(i-x+1);
    }
}

inline void Solve()
{
    int i,j,k;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
        {
            for(k=1;k<=m;k++)
                v[k]=s[j][k]-s[i-1][k];
            MaxSurface(i,j);
        }
    ofstream fout("teren.out");
    fout<<mx<<"\n";
    fout.close();
}

int main()
{
    Input();
    Create();
    Solve();
    return 0;
}