Cod sursa(job #1956008)

Utilizator cipri321Marin Ciprian cipri321 Data 6 aprilie 2017 13:40:47
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;
ifstream fi("teren.in");
ofstream fo("teren.out");
int n,m,x;
int A[301][301],C[301][301],sum;
int rez,st;
int k;
int main()
{
    fi>>n>>m>>x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            fi>>A[i][j];
            C[i][j]=C[i-1][j]+A[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            sum=0;
            k=1;
            while(true)
            {
                sum+=C[j][k]-C[i-1][k];
                if(sum>x||k==m+1)
                {
                    sum-=C[j][k]-C[i-1][k];
                    k--;
                    break;
                }
                k++;
            }
            rez=max(rez,(j-i+1)*k);
            st=1;
            for(;k<=m;k++)
            {
                sum+=C[j][k]-C[i-1][k];
                while(sum>x)
                {
                    sum-=C[j][st]-C[i-1][st];
                    st++;
                }
                rez=max(rez,(j-i+1)*(k-st+1));
            }
        }
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}