Cod sursa(job #677734)

Utilizator veleanduAlex Velea veleandu Data 10 februarie 2012 16:33:13
Problema Teren Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
// bla bla acta
#include <iostream>
#include <fstream>
using namespace std;
#define maxn 305
int S[305][305];
int T[305][305];
long x,y,c_dr,l_jos,n,m,k,maxim=-1,i,j,ok;

ifstream in("teren.in");
ofstream out("teren.out");

int main()
{
    in>>n>>m>>k;
    for ( i=1; i<=n; i++ )
        for ( j=1; j<=m; j++ )
            in>>T[i][j];
    for ( i=1; i<=n; i++ )
        for ( j=1; j<=m; j++ )
            S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+T[i][j];
    /*for ( i=1; i<=n; i++,cout<<"\n" )
        for ( j=1; j<=m; j++ )
            cout<<S[i][j]<<" ";*/
    for ( x=1; x<n; x++ ) // bla bla acta
        for ( y=1; y<m; y++ ) // bla bla acta
        {
            // mergem sa dam cu jandarmi in pietre
            // bla bla acta

            l_jos=n;
            ok=1;
            for ( c_dr=y; c_dr<=m && ok==1; c_dr++ )
            {
                while( ((S[l_jos][c_dr]-S[x-1][c_dr]-S[l_jos][y-1]+S[x-1][y-1]) >k ) && l_jos>x)
                {
                    l_jos--;
                }
                if (((S[l_jos][c_dr]-S[x-1][c_dr]-S[l_jos][y-1]+S[x-1][y-1]) >k ) )
                {
                    ok=0;
                }
                else{
                    if ((l_jos-x+1)*(1+c_dr-y)>maxim)
                        maxim=(l_jos-x+1)*(c_dr-y+1);
                }
            }
        }
    out<<maxim;
    return 0;
}