Cod sursa(job #2630124)

Utilizator eugen5092eugen barbulescu eugen5092 Data 24 iunie 2020 14:02:04
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;

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

short n,m;
int k;
bool v[500][500];
int sum[500][500];

inline void citire(){
    ci>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ci>>v[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+v[i][j];
            //cout<<sum[i][j]<<" ";
        }
        //cout<<"\n";
    }
}

inline void rez(){
    //cout<<"\n\n";
    int p,i,sm,arie=0;
    int st,dr;
    for(p=0;p<=n-1;p++){
        for(i=p+1;i<=n;i++){
            st=1;
            for(dr=1;dr<=m;dr++){
                sm=sum[i][dr]-sum[p][dr]-sum[i][st-1]+sum[p][st-1];
                while(sm>k){
                    sm-=sum[i][st]-sum[p][st];
                    st++;
                }
                //cout<<p<<" "<<i<<" "<<st<<" "<<dr<<"\n";
                arie=max(arie,(i-p)*(dr-st+1));
            }
        }
    }
    cou<<arie;

}

int main()
{
    citire();
    rez();
    return 0;
}