답안 #456437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456437	2021-08-06T17:39:05 Z	dxz05	Bomb (IZhO17_bomb)	C++14	49 / 100	1000 ms	55972 KB

bomb

#pragma GCC optimize("Ofast,O2,O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e6 + 3e2;
const int M = 2522;

int n, m;
int a[M][M];
bool bomb[M][M];
int dp[M][M];

int sum(int x1, int y1, int x2, int y2){
    if (min({x1, y1, x2, y2}) < 1 || max(x1, x2) > n || max(y1, y2) > m) return -1;
    assert(x1 <= x2 && y1 <= y2);
    int res = dp[x2][y2];
    res -= dp[x1 - 1][y2];
    res -= dp[x2][y1 - 1];
    res += dp[x1 - 1][y1 - 1];
    return res;
}

int ans = 0;

bool fill(int x1, int y1, int x2, int y2){
    if (sum(x1, y1, x2, y2) != (x2 - x1 + 1) * (y2 - y1 + 1)) return false;
    for (int i = x1; i <= x2; i++){
        for (int j = y1; j <= y2; j++){
            bomb[i][j] = true;
        }
    }
    return true;
}

bool check(int A, int B){
    //if (ans > A * B) return true;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) bomb[i][j] = false;
    }

    for (int i = 1; i <= n - A + 1; i++){
        for (int j = 1; j <= m - B + 1; j++){
            if (!a[i][j] || bomb[i][j]) continue;
            fill(i, j, i + A - 1, j + B - 1);
        }
    }

    for (int i = n; i >= A; i--){
        for (int j = 1; j <= m - B + 1; j++){
            if (!a[i][j] || bomb[i][j]) continue;
            fill(i - A + 1, j, i, j + B - 1);
        }
    }

    for (int i = 1; i <= n - A + 1; i++){
        for (int j = m; j >= B; j--){
            if (!a[i][j] || bomb[i][j]) continue;
            fill(i, j - B + 1, i + A - 1, j);
        }
    }

    for (int i = n; i >= A; i--){
        for (int j = m; j >= B; j--){
            if (!a[i][j] || bomb[i][j]) continue;
            fill(i - A + 1, j - B + 1, i, j);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] && !bomb[i][j]) return false;
        }
    }

    ans = max(ans, A * B);

    return true;
}

void solve(int TC) {
    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            char ch;
            cin >> ch;
            a[i][j] = ch - '0';
            dp[i][j] = dp[i][j - 1] + a[i][j];
        }
    }

    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; i++){
            dp[i][j] += dp[i - 1][j];
        }
    }

    int A = n, B = m;
    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; i++){
            if (a[i][j] == 0) continue;
            int k = i;
            while (k <= n && a[k][j] == 1) k++;
            A = min(A, k - i);
            i = k - 1;
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0) continue;
            int k = j;
            while (k <= m && a[i][k] == 1) k++;
            B = min(B, k - j);
            j = k - 1;
        }
    }

    if (check(A, B)){
        cout << ans;
        return;
    }

    if (A < B){
        for (int i = 1; i <= A; i++){
            int l = 1, r = B;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (check(i, mid)){
                    l = mid + 1;
                } else r = mid - 1;
            }
        }
    } else {
        for (int i = 1; i <= B; i++){
            int l = 1, r = A;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (check(mid, i)){
                    l = mid + 1;
                } else r = mid - 1;
            }
        }
    }

    cout << ans;

}

int main() {
    startTime = clock();
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
bomb.cpp:203:9: note: in expansion of macro 'debug'
  203 |         debug(test);
      |         ^~~~~

Subtask #1

49.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	14 ms	26496 KB	Output is correct
4	Correct	14 ms	26572 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct
10	Correct	1 ms	388 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	460 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	972 KB	Output is correct
18	Correct	1 ms	1100 KB	Output is correct
19	Correct	4 ms	1372 KB	Output is correct
20	Correct	5 ms	1356 KB	Output is correct
21	Correct	1 ms	844 KB	Output is correct
22	Correct	2 ms	1100 KB	Output is correct
23	Correct	8 ms	1356 KB	Output is correct
24	Correct	4 ms	1228 KB	Output is correct
25	Correct	12 ms	1460 KB	Output is correct
26	Correct	1 ms	1356 KB	Output is correct
27	Correct	4 ms	4044 KB	Output is correct
28	Correct	17 ms	4244 KB	Output is correct
29	Correct	478 ms	5384 KB	Output is correct
30	Correct	698 ms	6316 KB	Output is correct
31	Correct	400 ms	4940 KB	Output is correct
32	Correct	329 ms	5816 KB	Output is correct
33	Execution timed out	1078 ms	6624 KB	Time limit exceeded
34	Correct	19 ms	4684 KB	Output is correct
35	Correct	131 ms	6604 KB	Output is correct
36	Correct	8 ms	6588 KB	Output is correct
37	Correct	1 ms	460 KB	Output is correct
38	Correct	188 ms	55748 KB	Output is correct
39	Correct	1 ms	460 KB	Output is correct
40	Execution timed out	1075 ms	15440 KB	Time limit exceeded
41	Correct	1 ms	460 KB	Output is correct
42	Correct	17 ms	1456 KB	Output is correct
43	Correct	298 ms	55840 KB	Output is correct
44	Execution timed out	1088 ms	6604 KB	Time limit exceeded
45	Execution timed out	1092 ms	55724 KB	Time limit exceeded
46	Correct	272 ms	55796 KB	Output is correct
47	Execution timed out	1092 ms	55728 KB	Time limit exceeded
48	Execution timed out	1100 ms	55752 KB	Time limit exceeded
49	Correct	237 ms	55972 KB	Output is correct
50	Execution timed out	1094 ms	55780 KB	Time limit exceeded
51	Execution timed out	1092 ms	55748 KB	Time limit exceeded
52	Execution timed out	1089 ms	55748 KB	Time limit exceeded
53	Execution timed out	1092 ms	55904 KB	Time limit exceeded
54	Execution timed out	1085 ms	55876 KB	Time limit exceeded
55	Execution timed out	1093 ms	55752 KB	Time limit exceeded
56	Correct	197 ms	55788 KB	Output is correct
57	Execution timed out	1084 ms	55824 KB	Time limit exceeded
58	Execution timed out	1043 ms	55816 KB	Time limit exceeded
59	Execution timed out	1042 ms	55748 KB	Time limit exceeded
60	Correct	226 ms	55848 KB	Output is correct
61	Correct	230 ms	55816 KB	Output is correct
62	Correct	229 ms	55848 KB	Output is correct
63	Correct	202 ms	55744 KB	Output is correct
64	Correct	224 ms	55748 KB	Output is correct
65	Execution timed out	1077 ms	55756 KB	Time limit exceeded
66	Execution timed out	1084 ms	55748 KB	Time limit exceeded
67	Execution timed out	1097 ms	55768 KB	Time limit exceeded
68	Execution timed out	1092 ms	55816 KB	Time limit exceeded
69	Execution timed out	1095 ms	55780 KB	Time limit exceeded
70	Execution timed out	1088 ms	44612 KB	Time limit exceeded
71	Execution timed out	1092 ms	55720 KB	Time limit exceeded
72	Execution timed out	1080 ms	55796 KB	Time limit exceeded
73	Execution timed out	1088 ms	55740 KB	Time limit exceeded
74	Execution timed out	1090 ms	55804 KB	Time limit exceeded
75	Execution timed out	1093 ms	55716 KB	Time limit exceeded
76	Execution timed out	1059 ms	55876 KB	Time limit exceeded
77	Execution timed out	1095 ms	55748 KB	Time limit exceeded
78	Execution timed out	1082 ms	55748 KB	Time limit exceeded
79	Execution timed out	1057 ms	55724 KB	Time limit exceeded
80	Execution timed out	1088 ms	55748 KB	Time limit exceeded
81	Execution timed out	1087 ms	55848 KB	Time limit exceeded
82	Execution timed out	1080 ms	55812 KB	Time limit exceeded
83	Execution timed out	1097 ms	55788 KB	Time limit exceeded
84	Execution timed out	1035 ms	55740 KB	Time limit exceeded
85	Execution timed out	1093 ms	55796 KB	Time limit exceeded
86	Execution timed out	1085 ms	55724 KB	Time limit exceeded
87	Execution timed out	1093 ms	55832 KB	Time limit exceeded
88	Execution timed out	1086 ms	55744 KB	Time limit exceeded
89	Execution timed out	1091 ms	55748 KB	Time limit exceeded
90	Execution timed out	1090 ms	44716 KB	Time limit exceeded
91	Execution timed out	1096 ms	55816 KB	Time limit exceeded
92	Execution timed out	1089 ms	55796 KB	Time limit exceeded
93	Execution timed out	1100 ms	55748 KB	Time limit exceeded
94	Execution timed out	1094 ms	55792 KB	Time limit exceeded
95	Execution timed out	1085 ms	55780 KB	Time limit exceeded
96	Execution timed out	1092 ms	55820 KB	Time limit exceeded
97	Execution timed out	1100 ms	55808 KB	Time limit exceeded
98	Execution timed out	1057 ms	55812 KB	Time limit exceeded
99	Execution timed out	1089 ms	55744 KB	Time limit exceeded
100	Execution timed out	1095 ms	55740 KB	Time limit exceeded