Cod sursa(job #787409)

Utilizator vendettaSalajan Razvan vendetta Data 13 septembrie 2012 12:53:19
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("teren.in");
ofstream g("teren.out");

#define nmax 302

int n, m, X, sum[nmax][nmax];
bool a[nmax][nmax];

void citeste(){

	f >> n >> m >> X;
	for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            f >> a[i][j];
            sum[i][j] = sum[i-1][j] + a[i][j];
        }
	}

}

void rezolva(){

    //imi fixez 2 linii ; am precalculat sum[i][j] numarul de 1 de pe cooana j pana pe linia i;
    //am fixate 2 linii ma intereseaza cea mai lunga secventa cu nr de 1 mai mic sau egal cu X

    int rez = 0;
    for(int i=1; i<=n; ++i){
        for(int j=i; j<=n; ++j){
            int k2 = 1;
            int suma = 0;
            for(int k=1; k<=m; ++k){//iau fiecare coloana; si incerc sa gasesc dreptunghiul maxim ce se termina pe colaoana j
                int nr_de1 = sum[j][k] - sum[i-1][k];//nr de 1 de pe coloana k dintre liniie i, si j
                if (nr_de1 > X){// daca coloana asta are mai multi de 1 decat X
                    k2 = k+1;
                    suma = 0;
                }
                suma += nr_de1;
                while (suma > X){
                    int Y = sum[j][k2] - sum[i-1][k2];
                    suma -= Y;
                    k2++;
                }
                int inaltime = j-i+1;
                int lungime = k-k2+1;
                if (rez < inaltime * lungime){
                    rez = inaltime * lungime;
                }
            }
        }
    }

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}