Submission #831278

#	Time	Username	Problem	Language	Result	Execution time	Memory
831278		vjudge1	Bomb (IZhO17_bomb)	C++17	90 / 100	127 ms	55684 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//turn on extra precision
//#pragma GCC target("fpmath=387")

using namespace std;
using namespace __gnu_pbds;

using str   = string;
using ll    = long long;
using pii   = pair <int,int>;
using pll   = pair <ll,ll>;
using vi    = vector <int>;
using vll   = vector <ll>;
using vpii  = vector <pii>;
using vpll  = vector <pll>;

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    bool van = 1; os << '{';
    for(auto &i : v) { if(!van) os << ", "; os << i; van = 0; }
    os << '}'; return os;
}

template<class T, size_t sz>
ostream& operator<<(ostream&os, const array<T,sz> &arr) {
    bool fs = 1; os << '{';
    for(auto &i : arr) { if(!fs) os << ", "; os << i; fs = 0; }
    os << '}'; return os;
}

#define mp make_pair
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
#define all(x) x.begin(), x.end()
#define watch(x) cerr << (#x) << " is : " << (x) << newl

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
ll quickpow(ll num1, ll num2, const T MOD) {
    assert(num2 >= 0); ll ans = 1;
    for(; num2; num2>>=1, num1 = num1 * num1 % MOD) if(num2 & 1) ans = ans * num1 % MOD;
    return ans;
}
// end of Template

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<char>> grid(n, vector<char>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    vector<vector<int>> up(n, vector<int>(m)), dw(n, vector<int>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == '0') continue;
            up[i][j] = (i && grid[i-1][j] == '1' ? up[i-1][j] : i-1);
        }
    }

    for(int i = n - 1; i >= 0; --i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == '0') continue;
            dw[i][j] = (i + 1 < n && grid[i+1][j] == '1' ? dw[i+1][j] : i+1);
        }
    }

    const int INF = 1e9;
    vector<int> ver(m+1, INF);
    int maxh = m;
    for(int i = 0; i < n; ++i) {
        int L = INF;
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == '0') continue;

            int u = -1, d = INF, le = j - 1;
            int lenmax = 0;
            for(; j < m && grid[i][j] == '1'; ++j) {
                int len = j - le;
                u = max(u, up[i][j]);
                d = min(d, dw[i][j]);
                ver[len] = min(ver[len], d - u - 1);
                lenmax = max(lenmax, len);
            }
            L = min(L, lenmax);
        }
        maxh = min(maxh, L);

        for(int j = m - 1; j >= 0; --j) {
            if(grid[i][j] == '0') continue;

            int u = -1, d = INF, ri = j + 1;
            for(; j >= 0 && grid[i][j] == '1'; --j) {
                int len = ri - j;
                u = max(u, up[i][j]);
                d = min(d, dw[i][j]);
                ver[len] = min(ver[len], d - u - 1);
            }
        }
    }


    int ans = 0;
    for(int i = 1; i <= maxh; ++i) {
        if(ver[i] == INF) continue;
        ans = max(ans, i * ver[i]);
    }
    cout << ans << newl;

    return 0;
}

Compilation message (stderr)

bomb.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
bomb.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
bomb.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment(linker, "/stack:200000000")
      |

• Subtask 1: 90 / 100