Cod sursa(job #1726652)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 8 iulie 2016 16:38:01
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <math.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(){
    int n,m,j,k,i1,i2,X,ans,nr1;
    ans = 0;
    fin>>n>>m>>X;
    for(i1 = 1;i1 <= n;i1++){
        for(j = 1;j <= m;j++){
            fin>>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));
                }
            }
        }
    }
    fout<<ans;
    return 0;
}