Cod sursa(job #1588753)

Utilizator TimoteiCopaciu Timotei Timotei Data 3 februarie 2016 16:24:39
Problema Teren Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <iostream>
using namespace std;
int N, M, dp[303][303], X, x, mx, dr, st, mij;
int arie(int i, int j, int ii, int jj)
{
    int x = dp[i][j] - dp[i][jj - 1] - dp[ii - 1][j] + dp[ii - 1][jj - 1];
    return  x;
}
int main()
{
    ifstream f("teren.in");
    ofstream g("teren.out");
    f >> N >> M >> X;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++){
        f >> x;
        dp[i][j] = x + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    }
    for(int i = 1; i <= N; i++)
    for(int j = 1; j <= M; j++){
        for(int k = 1; k <= i; k++){
            dr = j;
            st = 1;
            while(st < dr){
                mij = (st + dr)/2;
                if(arie(i, j, k, mij) <= X) dr = mij - 1;
                else st = mij + 1;
            }
            if((i - k + 1)*(j - st + 1) > mx) mx = (i - k + 1)*(j - st + 1);
        }
    }
    g << mx;

    return 0;
}