Cod sursa(job #1162337)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 31 martie 2014 19:25:57
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>

using namespace std;

int n,m,X,i1,i2,i,j,sum,p,u,arie;

int A[301][301],S[301][301];

int main() {
    ifstream f("teren.in");
    ofstream g("teren.out");
    f>>m>>n>>X;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            f>>A[i][j];
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            S[i][j]=S[i-1][j]+A[i][j];
    for(i1=1;i1<=m;i1++)
        for(i2=i1;i2<=m;i2++) {
            p=1;
            sum=0;
            for(u=1;u<=n;u++) {
                sum+=S[i2][u]-S[i1-1][u];
                while(sum>X && p<=u) {
                    sum-=S[i2][p]-S[i1-1][p];
                    p++;
                }
                if(arie<(i2-i1+1)*(u-p+1))
                    arie=(i2-i1+1)*(u-p+1);
            }
        }
    g<<arie<<"\n";
    return 0;
}