Pagini recente » Cod sursa (job #1634894) | Cod sursa (job #2990042) | Cod sursa (job #3256962) | Cod sursa (job #1636516) | Cod sursa (job #777355)
Cod sursa(job #777355)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
#define nmax 202
int n, m, a[nmax][nmax], h[nmax][nmax], A[nmax], B[nmax], st[nmax], dr[nmax];
deque<int> dq;
void citeste(){
f >> n >> m;
f.get();
for(int i=1; i<=n; i++){
string s;
getline(f,s);
for(int j=0; j<m; j++) a[i][j+1] = (s[j] - '0');
}
}
void extindere_st(int linie){
dq.clear();
dq.push_back(0);
for(int j=1; j<=m; j++){
while(dq.size() && h[linie][ dq.back() ] >= h[linie][j] ) dq.pop_back();
if (dq.size() )st[j] = j-dq.back();//cat de mult ma pot duce in stanga avand un dreptunghi cu inaltimea h[i][j]
else st[j] = 0;
dq.push_back(j);
}
}
void extindere_dr(int linie){
dq.clear();
dq.push_back(m+1);
for(int j=m; j>=1; j--){
while(dq.size() && h[linie][ dq.back() ] >= h[linie][j] )dq.pop_back();
if (dq.size() )dr[j] = dq.back() - j;
else dr[j] = 0;
dq.push_back(j);
}
}
void rezolva(){
//trebuie sa determin 2 dreptunghiuri pline cu 0 care sa ocupe o arie maxima (iar aceste dreptunghiuri sa nu se suprapuna)
//o(n^3) iau fiecare linie(si coloana) si presupun ca un dreptunghi se afla dreasupra linie si celalalt dedesubt;
// aflu in n^2 drepuntghiul de arie maxima
//o(n^2) : precalculez pentru fiecare linie cel mai mare dreptunghi care se afla pana pe acea linie (inclusiv) vin de sus in jos
// cel mai mare drepuntghi care se afla pana pe acea linie(fara ea) vin jos in sus
//ma duc de sus in jos
//h[i][j] = cat de mult ma pot duce in sus eu fiind in (i,j)
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if (a[i][j] == 0) h[i][j] = h[i-1][j] + 1;
else h[i][j] = 0;
}
extindere_st(i);
extindere_dr(i);
A[i] = A[i-1];
for(int j=1; j<=m; j++){
int X = (st[j] + dr[j] - 1) * h[i][j];
A[i] = max(A[i], X);
//cout << dr[j] << " ";
}
//cout << A[i] << "\n";
//cout << "\n";
}
//vin de jos in sus
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) h[i][j] = 0;
for(int i=n; i>=1; i--){
for(int j=1; j<=m; j++){
if (a[i][j] == 0) h[i][j] = h[i+1][j] + 1;
else h[i][j] = 0;
}
extindere_st(i);
extindere_dr(i);
B[i] = B[i+1];
for(int j=1; j<=m; j++){
int X = (st[j] + dr[j] - 1 ) * h[i][j];
B[i] = max(B[i], X);
}
}
//iau fiecare linie si presuspun ca primul e deasupra incepand cu linia si celalalt dedesubt (fara linie)
int rez = 0;
for(int i=1; i<=n; i++){
if (rez < A[i] + B[i+1]) rez = A[i] + B[i+1];
}
g << rez << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}