Submission #1162050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162050		jahongir	Bomb (IZhO17_bomb)	C++20	100 / 100	226 ms	50560 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;

template<class T> using ormset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
#define f first
#define s second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define popcount __builtin_popcount
#define pi pair<int,int>

void setIO(string name = ""){
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    if(name.empty()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }else{
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

const int mxn = 3e3;
bitset<mxn> grid[mxn];
int n,m;


void solve(){

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            grid[i][j] = c=='1';
        }
    }
    vector<vector<int>> left(n,vector<int>(m,0));
    vector<vector<int>> right(n,vector<int>(m,0));
    
    vector<int> mxwid(n+1,m+1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            if(grid[i][j])
                left[i][j] = left[i][max(0,j-1)]+1;
        for(int j = m-1; j >= 0; j--)
            if(grid[i][j]){
                right[i][j] = right[i][min(m-1,j+1)]+1;
                mxwid[1] = min(mxwid[1],right[i][j]+left[i][j]-1);
            }
    }

    int mxhe = n+1;
    for(int j = 0; j < m; j++){
        int cnt = 0;
        int l = m, r = m;
        for(int i = 0; i < n; i++){
            if(grid[i][j]){
                l = min(l,left[i][j]);
                r = min(r,right[i][j]);
                cnt++;
                mxwid[cnt] = min(mxwid[cnt],l+r-1);
            }else{
                if(cnt) mxhe = min(mxhe,cnt);
                cnt = 0;
                l = r = m;
            }
        }
        if(cnt) mxhe = min(mxhe,cnt);
        cnt = 0, l = r = m;
        for(int i = n-1; i >= 0; i--){
            if(grid[i][j]){
                l = min(l,left[i][j]);
                r = min(r,right[i][j]);
                cnt++;
                mxwid[cnt] = min(mxwid[cnt],l+r-1);
            }else{
                if(cnt) mxhe = min(mxhe,cnt);
                cnt = 0;
                l = r = m;
            }
        }
        if(cnt) mxhe = min(mxhe,cnt);
    }

    int ans = 0;
    for(int i = 1; i <= mxhe; i++){
        mxwid[i] = min(mxwid[i],mxwid[i-1]);
        ans = max(ans,mxwid[i]*i);
    }
    cout << ans;
}


int main(){
    // setIO("bomb");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

bomb.cpp: In function 'void setIO(std::string)':
bomb.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100