oj.uz

답안 #833968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833968 2023-08-22T09:53:10 Z vjudge1 Bomb (IZhO17_bomb) C++14
52 / 100
 161 ms 55756 KB 
#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;
}

Compilation message

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 0 ms 340 KB Output isn't correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Incorrect 0 ms 340 KB Output isn't correct
25 Incorrect 1 ms 340 KB Output isn't correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 980 KB Output is correct
28 Incorrect 2 ms 1236 KB Output isn't correct
29 Incorrect 3 ms 1364 KB Output isn't correct
30 Incorrect 3 ms 2004 KB Output isn't correct
31 Correct 3 ms 1620 KB Output is correct
32 Incorrect 3 ms 1620 KB Output isn't correct
33 Incorrect 5 ms 2132 KB Output isn't correct
34 Incorrect 2 ms 980 KB Output isn't correct
35 Incorrect 4 ms 2132 KB Output isn't correct
36 Correct 6 ms 2132 KB Output is correct
37 Incorrect 0 ms 212 KB Output isn't correct
38 Correct 120 ms 55636 KB Output is correct
39 Incorrect 0 ms 212 KB Output isn't correct
40 Correct 13 ms 7124 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 115 ms 55640 KB Output is correct
44 Correct 5 ms 2148 KB Output is correct
45 Incorrect 124 ms 55636 KB Output isn't correct
46 Correct 114 ms 55640 KB Output is correct
47 Incorrect 113 ms 55640 KB Output isn't correct
48 Correct 108 ms 55636 KB Output is correct
49 Correct 109 ms 55640 KB Output is correct
50 Correct 112 ms 55756 KB Output is correct
51 Correct 106 ms 55628 KB Output is correct
52 Correct 110 ms 55628 KB Output is correct
53 Correct 108 ms 55544 KB Output is correct
54 Correct 106 ms 55644 KB Output is correct
55 Incorrect 100 ms 55636 KB Output isn't correct
56 Correct 115 ms 55756 KB Output is correct
57 Incorrect 105 ms 55532 KB Output isn't correct
58 Correct 106 ms 55640 KB Output is correct
59 Correct 99 ms 55536 KB Output is correct
60 Correct 109 ms 55536 KB Output is correct
61 Correct 124 ms 55532 KB Output is correct
62 Correct 113 ms 55628 KB Output is correct
63 Correct 113 ms 55640 KB Output is correct
64 Correct 156 ms 55612 KB Output is correct
65 Correct 108 ms 55628 KB Output is correct
66 Correct 113 ms 55660 KB Output is correct
67 Correct 110 ms 55628 KB Output is correct
68 Correct 114 ms 55532 KB Output is correct
69 Correct 112 ms 55532 KB Output is correct
70 Incorrect 79 ms 35708 KB Output isn't correct
71 Incorrect 109 ms 55660 KB Output isn't correct
72 Incorrect 132 ms 55640 KB Output isn't correct
73 Correct 108 ms 55636 KB Output is correct
74 Incorrect 119 ms 55640 KB Output isn't correct
75 Incorrect 107 ms 55732 KB Output isn't correct
76 Incorrect 104 ms 55628 KB Output isn't correct
77 Incorrect 105 ms 55648 KB Output isn't correct
78 Incorrect 103 ms 55516 KB Output isn't correct
79 Incorrect 154 ms 55536 KB Output isn't correct
80 Incorrect 99 ms 55548 KB Output isn't correct
81 Incorrect 115 ms 55636 KB Output isn't correct
82 Incorrect 103 ms 55628 KB Output isn't correct
83 Incorrect 104 ms 55640 KB Output isn't correct
84 Incorrect 99 ms 55528 KB Output isn't correct
85 Incorrect 104 ms 55640 KB Output isn't correct
86 Incorrect 113 ms 55628 KB Output isn't correct
87 Incorrect 113 ms 55512 KB Output isn't correct
88 Correct 108 ms 55644 KB Output is correct
89 Correct 105 ms 55628 KB Output is correct
90 Incorrect 70 ms 35772 KB Output isn't correct
91 Incorrect 117 ms 55640 KB Output isn't correct
92 Incorrect 114 ms 55636 KB Output isn't correct
93 Incorrect 112 ms 55544 KB Output isn't correct
94 Correct 123 ms 55640 KB Output is correct
95 Incorrect 109 ms 55628 KB Output isn't correct
96 Correct 110 ms 55600 KB Output is correct
97 Incorrect 112 ms 55544 KB Output isn't correct
98 Incorrect 103 ms 55528 KB Output isn't correct
99 Incorrect 109 ms 55540 KB Output isn't correct
100 Incorrect 161 ms 55644 KB Output isn't correct