Pagini recente » Cod sursa (job #2692757) | Cod sursa (job #1797357) | Cod sursa (job #1787291) | Cod sursa (job #1083316) | Cod sursa (job #1711255)
#include <fstream>
#include <cstring>
#define DIM 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
short int dp1[DIM][DIM][DIM] , dp2[DIM][DIM][DIM] , lastst[DIM][DIM] , lastdr[DIM][DIM] , ans1[DIM][DIM] , ans2[DIM][DIM];
short int n , m , sol;
char mat[DIM][DIM];
int min(short int a , short int b) {
if(a < b)
return a;
return b;
}
int max(short int a , short int b) {
if(a > b)
return a;
return b;
}
int main() {
f >> n >> m;
for(short int i = 1 ; i <= n ; ++i) {
f >> mat[i] + 1;
}
for(short int i = 1 ; i <= n ; ++i) {
for(short int j = 1 ; j <= m ; ++j) {
if(mat[i][j] == '1') {
lastst[i][j] = 0;
}
else {
lastst[i][j] = lastst[i][j - 1] + 1;
}
}
for(short int j = m ; j >= 1 ; --j) {
if(mat[i][j] == '1') {
lastdr[i][j] = 0;
}
else {
lastdr[i][j] = lastdr[i][j + 1] + 1;
}
}
}
for(short int i = 1 ; i <= n ; ++i) {
for(short int j = 1 ; j <= m ; ++j) {
for(short int k = 2 ; k <= i ; ++k) {
dp1[i][j][k] = min(dp1[i - 1][j][k - 1] , lastst[i][j]);
ans1[i][j] = max(ans1[i][j] , dp1[i][j][k] * k);
}
dp1[i][j][1] = lastst[i][j];
ans1[i][j] = max(ans1[i][j] , dp1[i][j][1]);
ans1[i][j] = max(ans1[i][j] , max(ans1[i - 1][j] , ans1[i][j - 1]));
}
}
for(short int i = n ; i >= 1 ; --i) {
for(short int j = m ; j >= 1; --j) {
for(short int k = 2 ; k <= n - i + 1 ; ++k) {
dp2[i][j][k] = min(dp2[i + 1][j][k - 1] , lastdr[i][j]);
ans2[i][j] = max(ans2[i][j] , dp2[i][j][k] * k);
}
dp2[i][j][1] = lastdr[i][j];
ans2[i][j] = max(ans2[i][j] , dp2[i][j][1]);
ans2[i][j] = max(ans2[i][j] , max(ans2[i + 1][j] , ans2[i][j + 1]));
}
}
for(short int lin = 1 ; lin < n ; ++lin) {
short int s1 = ans1[lin][m];
short int s2 = ans2[lin + 1][1];
sol = max(sol , s1 + s2);
}
memset(ans1 , 0 , sizeof(ans1));
memset(ans2 , 0 , sizeof(ans2));
memset(dp1 , 0 , sizeof(dp1));
memset(dp2 , 0 , sizeof(dp2));
for(short int i = 1 ; i <= n ; ++i) {
for(short int j = m ; j >= 1 ; +--j) {
for(short int k = 2 ; k <= i ; ++k) {
dp1[i][j][k] = min(dp1[i - 1][j][k - 1] , lastdr[i][j]);
ans1[i][j] = max(ans1[i][j] , dp1[i][j][k] * k);
}
dp1[i][j][1] = lastdr[i][j];
ans1[i][j] = max(ans1[i][j] , dp1[i][j][1]);
ans1[i][j] = max(ans1[i][j] , max(ans1[i - 1][j] , ans1[i][j + 1]));
}
}
for(short int i = n ; i >= 1 ; --i) {
for(short int j = 1 ; j <= m; ++j) {
for(short int k = 2 ; k <= n - i + 1 ; ++k) {
dp2[i][j][k] = min(dp2[i + 1][j][k - 1] , lastst[i][j]);
ans2[i][j] = max(ans2[i][j] , dp2[i][j][k] * k);
}
dp2[i][j][1] = lastst[i][j];
ans2[i][j] = max(ans2[i][j] , dp2[i][j][1]);
ans2[i][j] = max(ans2[i][j] , max(ans2[i + 1][j] , ans2[i][j - 1]));
}
}
for(short int col = 1 ; col < m ; ++col) {
short int s1 = ans2[1][col + 1];
short int s2 = ans1[col][n];
sol = max(sol , s1 + s2);
}
g << sol;
return 0;
}