Pagini recente » Cod sursa (job #2648285) | Cod sursa (job #1500948) | Cod sursa (job #285852) | Cod sursa (job #1273943) | Cod sursa (job #1512648)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void find_best_matrix_up(const vector<vector<bool> >& v, vector<int>& rez){
const int n = v.size(), m = v[0].size();
vector<int> adanc(m, 0), len_st(m, 0), st(n);
rez.resize(n, 0);
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
adanc[j] = (v[i][j] ? 0 : adanc[j]+1); }
st.clear();
for(int j = 0; j < m; ++j){
while(!st.empty() && adanc[st.back()] >= adanc[j]){
st.pop_back(); }
len_st[j] = (st.empty() ? j : j-st.back()-1);
st.push_back(j); }
rez[i] = (i == 0 ? 0 : rez[i-1]);
st.clear();
for(int j = m-1; j >= 0; --j){
while(!st.empty() && adanc[st.back()] >= adanc[j]){
st.pop_back(); }
int len_dr = (st.empty() ? m-1-j : st.back()-j-1);
rez[i] = max(rez[i], (len_st[j]+len_dr+1) * adanc[j]);
st.push_back(j); } } }
template <typename V>
void print(const V v){
for(const auto x : v){
for(const auto y : x){
cout << y;}
cout << endl; }
cout << endl; }
int main(){
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n, m;
f >> n >> m >> ws;
vector<vector<bool> > v(n, vector<bool>(m, false)), inv_v(n, vector<bool>(m, false)),
v_t(m, vector<bool>(n, false)), inv_v_t(m, vector<bool>(n, false));
char buf[256];
for(int i = 0; i < n; ++i){
f.read(&buf[0], m);
f.ignore();
for(int j = 0; j < m; ++j){
v[i][j] = inv_v[n-i-1][j] = v_t[j][i] = inv_v_t[m-j-1][i] = (buf[j] == '1'); } }
vector<int> best_v, best_inv_v, best_v_t, best_inv_v_t;
find_best_matrix_up(v, best_v);
find_best_matrix_up(inv_v, best_inv_v);
find_best_matrix_up(v_t, best_v_t);
find_best_matrix_up(inv_v_t, best_inv_v_t);
int best = 0;
for(int i = 0; i+1 < n; ++i){
best = max(best, best_v[i] + best_inv_v[n-i-2]); }
for(int i = 0; i+1 < m; ++i){
best = max(best, best_v_t[i] + best_inv_v_t[m-i-2]); }
g << best;
return 0; }