Pagini recente » Cod sursa (job #959198) | Cod sursa (job #2627150) | Cod sursa (job #2979203) | Cod sursa (job #1676096) | Cod sursa (job #775157)
Cod sursa(job #775157)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
#define nmax 202
int m, n, a[nmax][nmax], h[nmax][nmax], st[nmax], dr[nmax];
deque<int> dq;
void citeste(){
f >> m >> n;
f.get();
for(int i=1; i<=m; i++){
string s;
s.clear();
getline(f,s);
for(int j=0; j<s.size(); j++){
if (s[j] == '1') a[i][j+1] = 1;
else a[i][j+1] = 0;
}
}
}
void rezolva(){
//am nevoie de 2 dreptunghiuri care nu se suprapun si ocupa impreuna o arie cat mai mare;
//pt a nu se suprapune aleg toate posibilitaile de a alege 2 dreptunghiuri : aleg o linie si presupun ca un dreptunghi sa fie dreasupra celelat dedesubt
//aleg o coloana si presupun ca un dreptunghi sa fie la stanga / la dreapta acestei coloane
//aflu dreptunghiul de arie maxima in m*n
//preprocesez pentru fiecare i,j cate de mult ma pot duce in sus daca ma aflu in i,j
//acum ma intereseaza cat de mult ma pot duce in stanga/si indreapta AVAND INALTIMEA DREPTUNGHIULUI LA FEL CA h[i][j];
//e corect pt ca : apare cazul cand eu sunt in (i,j) si am inaltimea h[i][j]; si ma duc la stanga 1 pasi iar la dreapta 1 pas :
//astfel se form un dreptunghi de h[i][j] * 3; dar daca alegeam o inaltime mai mica puteam sa formez un dreptunghi mai mare;
//DAR acest dreptunghi oricum se va forma cand ajung la coloana respectiva;
//deci ma duc in stanga si in dreapta atata timp cat coloane au o inaltime mai mare sau cel putin egale cu inaltimea mea
//aleg o linie acum
//primul dreptunghi se termina cel mult pe linia i iar al doilea incepe cel mult pe linia i+1
int rez = 0;
for(int linie = 1; linie<m; linie++){
//primul dreptunghi
int rez1 = 0;
int rez2 = 0;
for(int j=1; j<=n; j++) h[linie][j] = 0, st[j] = 0, dr[j] = 0;
for(int i=1; i<=linie; i++){
// aflu pentru fiecare cat de mult ma pot duce in sus
for(int j=1; j<=n; j++){
if (a[i][j] == 1){
h[i][j] = 0;
continue;
}
h[i][j] = h[i-1][j] + 1;
}
//acum aflu extinderea la dreapta si la stanga a elementului i,j
//la dreapta(=> vin din dreapta)
dq.clear();
dq.push_back(n+1);
h[i][n+1] = -1;//cazul cand o coloana poate merge pana in capat
for(int j=n; j>=1; j--){
//if (a[i][j] == 1) continue;
while( dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
dr[j] = dq.back()-1;//asta imi da prima coloana mai mica strict ca si a mea =>
//pana la aceasta coloana toate au fost mai mari sau cel putin egal cu mea
dq.push_back(j);
}
// la stanga
dq.clear();
dq.push_back(0);
h[i][0] = -1;
for(int j=1; j<=n; j++){
//if (a[i][j] == 1) continue;
while(dq.size() && h[i][j] <= h[i][dq.back()] ) dq.pop_back();
st[j] = dq.back()+1;
dq.push_back(j);
}
//calculez pentru fiecare cooana dreptunghiul cu h = h[i][j]
for(int j=1; j<=n; j++){
if (a[i][j] == 1) continue;
//if (linie == 2 && i == 2)cout << j << " " << st[j] << " " << dr[j] << "\n";
int St = j-st[j]+1;//cate coloana sunt intre st[j] si j
int Dr = dr[j]-j + 1;
int Total = St + Dr-1; // -1 pt ca coloana j a fost pusa de 2 ori
if (rez1 < h[i][j] * Total){
rez1 = h[i][j] * Total;
}
}
}
for(int j=1; j<=n; j++) h[linie][j] = 0, st[j] = 0, dr[j] = 0;
for(int i=linie+1; i<=m; i++){
for(int j=1; j<=n; j++){
if (a[i][j] == 1){
h[i][j] = 0;
//continue;
}
else h[i][j] = h[i-1][j] + 1;
}
dq.clear();
h[i][n+1] = -1;
dq.push_back(n+1);
//la dreapta
for(int j=n; j>=1; j--){
//if (a[i][j] == 1) continue;
while(dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
dr[j] = dq.back() -1;
dq.push_back(j);
}
dq.clear();
h[i][0] = -1;
dq.push_back(0);
//la stanga
for(int j=1; j<=n; j++){
//if (a[i][j] == 1) continue;
while(dq.size() && h[i][j] <= h[i][dq.back()]) dq.pop_back();
st[j] = dq.back() + 1;
dq.push_back(j);
}
//total
for(int j=1; j<=n; j++){
if (a[i][j] == 1) continue;
int St = j-st[j] + 1;
int Dr = dr[j] - j +1;
int Total = St + Dr - 1;
if (rez2 < h[i][j] * Total){
rez2 = h[i][j] * Total;
}
}
}
if (rez < rez1 + rez2){
rez = rez1 + rez2;
}
}
g << rez << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}