답안 #456315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456315	2021-08-06T11:53:41 Z	dxz05	Bomb (IZhO17_bomb)	C++14	43 / 100	1000 ms	55996 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, y1, x2, y2}) > n) 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 = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (!a[i][j] || bomb[i][j]) continue;
            if (fill(i, j, i + A - 1, j + B - 1)) continue;
            if (fill(i - A + 1, j, i, j + B - 1)) continue;
            if (fill(i, j - B + 1, i + A - 1, j)) continue;
            if (fill(i - A + 1, j - B + 1, i, j)) continue;
            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:187:9: note: in expansion of macro 'debug'
  187 |         debug(test);
      |         ^~~~~

Subtask #1

43.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	332 KB	Output isn't correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	13 ms	26524 KB	Output is correct
4	Correct	15 ms	26516 KB	Output is correct
5	Incorrect	1 ms	332 KB	Output isn't correct
6	Incorrect	0 ms	332 KB	Output isn't correct
7	Correct	1 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	460 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	Incorrect	1 ms	972 KB	Output isn't correct
18	Correct	1 ms	1100 KB	Output is correct
19	Incorrect	2 ms	1356 KB	Output isn't correct
20	Correct	2 ms	1356 KB	Output is correct
21	Correct	1 ms	844 KB	Output is correct
22	Correct	1 ms	1100 KB	Output is correct
23	Correct	5 ms	1480 KB	Output is correct
24	Correct	2 ms	1228 KB	Output is correct
25	Correct	7 ms	1356 KB	Output is correct
26	Correct	1 ms	1356 KB	Output is correct
27	Correct	4 ms	4044 KB	Output is correct
28	Correct	10 ms	4172 KB	Output is correct
29	Correct	301 ms	5396 KB	Output is correct
30	Correct	260 ms	6216 KB	Output is correct
31	Correct	157 ms	4940 KB	Output is correct
32	Correct	122 ms	5708 KB	Output is correct
33	Correct	503 ms	6624 KB	Output is correct
34	Correct	10 ms	4704 KB	Output is correct
35	Correct	36 ms	6604 KB	Output is correct
36	Correct	8 ms	6640 KB	Output is correct
37	Correct	1 ms	460 KB	Output is correct
38	Correct	202 ms	55776 KB	Output is correct
39	Correct	1 ms	460 KB	Output is correct
40	Execution timed out	1084 ms	15436 KB	Time limit exceeded
41	Incorrect	1 ms	460 KB	Output isn't correct
42	Correct	11 ms	1484 KB	Output is correct
43	Correct	512 ms	55844 KB	Output is correct
44	Execution timed out	1079 ms	6556 KB	Time limit exceeded
45	Execution timed out	1061 ms	55812 KB	Time limit exceeded
46	Correct	211 ms	55844 KB	Output is correct
47	Execution timed out	1093 ms	55856 KB	Time limit exceeded
48	Execution timed out	1096 ms	55752 KB	Time limit exceeded
49	Correct	228 ms	55796 KB	Output is correct
50	Execution timed out	1093 ms	55748 KB	Time limit exceeded
51	Execution timed out	1074 ms	55748 KB	Time limit exceeded
52	Execution timed out	1091 ms	55776 KB	Time limit exceeded
53	Execution timed out	1088 ms	55748 KB	Time limit exceeded
54	Execution timed out	1088 ms	55876 KB	Time limit exceeded
55	Execution timed out	1082 ms	55808 KB	Time limit exceeded
56	Correct	212 ms	55876 KB	Output is correct
57	Execution timed out	1095 ms	55808 KB	Time limit exceeded
58	Execution timed out	1094 ms	55772 KB	Time limit exceeded
59	Execution timed out	1088 ms	55748 KB	Time limit exceeded
60	Correct	212 ms	55876 KB	Output is correct
61	Execution timed out	1084 ms	55808 KB	Time limit exceeded
62	Correct	237 ms	55772 KB	Output is correct
63	Correct	213 ms	55824 KB	Output is correct
64	Correct	212 ms	55748 KB	Output is correct
65	Execution timed out	1090 ms	55784 KB	Time limit exceeded
66	Execution timed out	1082 ms	55716 KB	Time limit exceeded
67	Execution timed out	1053 ms	55820 KB	Time limit exceeded
68	Execution timed out	1083 ms	55748 KB	Time limit exceeded
69	Execution timed out	1092 ms	55768 KB	Time limit exceeded
70	Execution timed out	1093 ms	44684 KB	Time limit exceeded
71	Execution timed out	1084 ms	55820 KB	Time limit exceeded
72	Execution timed out	1066 ms	55808 KB	Time limit exceeded
73	Execution timed out	1095 ms	55816 KB	Time limit exceeded
74	Execution timed out	1099 ms	55736 KB	Time limit exceeded
75	Execution timed out	1082 ms	55752 KB	Time limit exceeded
76	Execution timed out	1094 ms	55864 KB	Time limit exceeded
77	Execution timed out	1086 ms	55748 KB	Time limit exceeded
78	Execution timed out	1084 ms	55808 KB	Time limit exceeded
79	Execution timed out	1091 ms	55736 KB	Time limit exceeded
80	Execution timed out	1088 ms	55812 KB	Time limit exceeded
81	Execution timed out	1086 ms	55876 KB	Time limit exceeded
82	Execution timed out	1090 ms	55812 KB	Time limit exceeded
83	Execution timed out	1024 ms	55816 KB	Time limit exceeded
84	Execution timed out	1081 ms	55816 KB	Time limit exceeded
85	Execution timed out	1058 ms	55740 KB	Time limit exceeded
86	Execution timed out	1076 ms	55720 KB	Time limit exceeded
87	Execution timed out	1051 ms	55736 KB	Time limit exceeded
88	Execution timed out	1099 ms	55852 KB	Time limit exceeded
89	Execution timed out	1073 ms	55996 KB	Time limit exceeded
90	Execution timed out	1085 ms	44612 KB	Time limit exceeded
91	Execution timed out	1095 ms	55808 KB	Time limit exceeded
92	Execution timed out	1091 ms	55744 KB	Time limit exceeded
93	Execution timed out	1078 ms	55744 KB	Time limit exceeded
94	Execution timed out	1087 ms	55748 KB	Time limit exceeded
95	Execution timed out	1097 ms	55812 KB	Time limit exceeded
96	Execution timed out	1097 ms	55748 KB	Time limit exceeded
97	Execution timed out	1087 ms	55812 KB	Time limit exceeded
98	Execution timed out	1097 ms	55748 KB	Time limit exceeded
99	Execution timed out	1075 ms	55808 KB	Time limit exceeded
100	Execution timed out	1086 ms	55748 KB	Time limit exceeded