Cod sursa(job #1571521)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 18 ianuarie 2016 09:52:18
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 305;

int D[NMax][NMax];

inline int Binary(const int &l, int lo, int hi, const int &value){
    int mid, best;
    while(lo <= hi){
        mid = (lo + hi) >> 1;
        if(D[l][mid] <= value){
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}

int main(){
    int n, m, x;
    fin >> n >> m >> x;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> D[i][j];
            D[i][j] += (D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1]);
        }
    }
    int area, best;
    best = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = i; k <= n; k++){
                area = (k - i + 1) * (Binary(k, j, m, D[i][j] + x) - j + 1);
                best = max(best, area);
            }
        }
    }
    fout << best;
    return 0;
}