Pagini recente » Cod sursa (job #2892432) | Cod sursa (job #663412) | Cod sursa (job #1374827) | Cod sursa (job #2437486) | Cod sursa (job #787409)
Cod sursa(job #787409)
#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;
}