Pagini recente » Cod sursa (job #2404315) | Cod sursa (job #3295458) | Cod sursa (job #2636106) | Cod sursa (job #1249256) | Cod sursa (job #777359)
Cod sursa(job #777359)
#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], sus[nmax], jos[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 extindere_sus_2(int coloana){
dq.clear();
dq.push_back(0);
for(int i=1; i<=n; i++){
while(dq.size() && h[ dq.back() ][coloana] >= h[i][coloana]) dq.pop_back();
if (dq.size() ) sus[i] = i-dq.back();
else sus[i] = 0;
dq.push_back(i);
}
}
void extindere_jos_2(int coloana){
dq.clear();
dq.push_back(n+1);
for(int i=n; i>=1; i--){
while(dq.size() && h[ dq.back() ][coloana] >= h[i][coloana]) dq.pop_back();
if( dq.size() ) jos[i] = dq.back() - i;
else jos[i] = 0;
dq.push_back(i);
}
}
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=0; i<=n; i++){
if (rez < A[i] + B[i+1]) rez = A[i] + B[i+1];
}
//acum iau fiecare coloana
//vin de la stanga la dreapta
//ca sa fie mai usor rastorn drepuntghiul => inaltimea in noul drepuntghi sa o fie defapt cat ma pot duce la stanga eu fiind in (i,j)...etc
for(int j=1; j<=m; j++){
for(int i=1; i<=n; i++){
if (a[i][j] == 0) h[i][j] = h[i][j-1]+1;
else h[i][j] = 0;
}
extindere_sus_2(j);
extindere_jos_2(j);
A[j] = A[j-1];
for(int i=1; i<=n; i++){
int X = (sus[i] + jos[i] - 1) *h[i][j];
A[j] = max(A[j], X);
//cout << h[i][j] << " ";
}
//cout << "\n";
//cout << A[j] << "\n";
}
//vin de la dreapta la stanga
for(int j=m; j>=1; j--){
for(int i=1; i<=n; i++){
if (a[i][j] == 0) h[i][j] = h[i][j+1] + 1;
else h[i][j] = 0;
}
extindere_sus_2(j);
extindere_jos_2(j);
B[j] = B[j+1];
for(int i=1; i<=n; i++){
int X = (sus[i] + jos[i] - 1) * h[i][j];
B[j] = max(B[j], X);
}
}
//iau fiecare coloana
for(int j=0; j<=m; j++){
rez = max(rez, A[j] + B[j+1]);
}
g << rez << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}