Cod sursa(job #1726653)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 8 iulie 2016 16:40:02
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <math.h>
#include <stdio.h>

using namespace std;
#define ll long long
#define llu long long unsigned
#define pb push_back
#define mp make_pair

//string problemName = "teren";
//string inFile = problemName+".in";
//string outFile = problemName+".out";
//ifstream fin(inFile.c_str());
//ofstream fout(outFile.c_str());

int dp[305][305];

int main(){
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);
    int n,m,j,k,i1,i2,X,ans,nr1;
    ans = 0;
    scanf("%d %d %d",&n,&m,&X);
    for(i1 = 1;i1 <= n;i1++){
        for(j = 1;j <= m;j++){
            scanf("%d",&k);
            dp[i1][j] = dp[i1][j-1]+k;
        }
    }
    for(j = 1;j <= m;j++){
        for(k = j;k <=  m;k++){
            i1 = 1;
            nr1 = 0;
            for(i2 = 1;i2 <= n;i2++){
                nr1 += dp[i2][k]-dp[i2][j-1];
                while(nr1 > X && i1 <= i2){
                    nr1 -= dp[i1][k]-dp[i1][j-1];
                    i1++;
                }
                if(i1 <= i2){
                    ans = max(ans, (k-j+1)*(i2-i1+1));
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}