제출 #833968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833968		vjudge1	Bomb (IZhO17_bomb)	C++14	52 / 100	161 ms	55756 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 cur = 0;
 
    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];
            cur += grid[i][j] == '1';
        }
    }
 
    assert(cur);
 
    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;
 
    int maxv = INF;
    for(int j = 0; j < m; ++j) {
        int L = INF;
 
        int len = 0;
        for(int i = 0; i < n; ++i) {
            if(grid[i][j] == '0') {
                if(len) L = min(L, len);
                len = 0;
            }
            else ++len;
        }
        if(len) L = min(L, len);
 
 
        maxv = min(maxv, L);
    }
 
    vector<int> ver(m+1, maxv);
    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;
}

컴파일 시 표준 에러 (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: 52 / 100