답안 #456434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456434	2021-08-06T17:35:54 Z	dxz05	Bomb (IZhO17_bomb)	C++14	50 / 100	1000 ms	57220 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

50.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	13 ms	26572 KB	Output is correct
4	Correct	13 ms	26484 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is 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	Correct	1 ms	972 KB	Output is correct
18	Correct	1 ms	1100 KB	Output is correct
19	Correct	4 ms	1292 KB	Output is correct
20	Correct	4 ms	1372 KB	Output is correct
21	Correct	1 ms	844 KB	Output is correct
22	Correct	2 ms	1096 KB	Output is correct
23	Correct	7 ms	1356 KB	Output is correct
24	Correct	3 ms	1228 KB	Output is correct
25	Correct	10 ms	1356 KB	Output is correct
26	Correct	1 ms	1356 KB	Output is correct
27	Correct	5 ms	4044 KB	Output is correct
28	Correct	17 ms	4360 KB	Output is correct
29	Correct	277 ms	5512 KB	Output is correct
30	Correct	581 ms	6476 KB	Output is correct
31	Correct	307 ms	5068 KB	Output is correct
32	Correct	264 ms	5864 KB	Output is correct
33	Correct	781 ms	6732 KB	Output is correct
34	Correct	16 ms	4684 KB	Output is correct
35	Correct	101 ms	6824 KB	Output is correct
36	Correct	9 ms	6728 KB	Output is correct
37	Correct	1 ms	460 KB	Output is correct
38	Correct	191 ms	57000 KB	Output is correct
39	Correct	1 ms	460 KB	Output is correct
40	Execution timed out	1087 ms	15988 KB	Time limit exceeded
41	Correct	1 ms	460 KB	Output is correct
42	Correct	11 ms	1472 KB	Output is correct
43	Correct	300 ms	57160 KB	Output is correct
44	Execution timed out	1084 ms	6852 KB	Time limit exceeded
45	Execution timed out	1082 ms	56968 KB	Time limit exceeded
46	Correct	241 ms	57100 KB	Output is correct
47	Execution timed out	1080 ms	57048 KB	Time limit exceeded
48	Execution timed out	1036 ms	57028 KB	Time limit exceeded
49	Correct	242 ms	57048 KB	Output is correct
50	Execution timed out	1078 ms	57140 KB	Time limit exceeded
51	Execution timed out	1076 ms	57028 KB	Time limit exceeded
52	Execution timed out	1080 ms	57028 KB	Time limit exceeded
53	Execution timed out	1082 ms	56900 KB	Time limit exceeded
54	Execution timed out	1084 ms	56900 KB	Time limit exceeded
55	Execution timed out	1074 ms	56900 KB	Time limit exceeded
56	Correct	212 ms	56896 KB	Output is correct
57	Execution timed out	1078 ms	56904 KB	Time limit exceeded
58	Execution timed out	1053 ms	56992 KB	Time limit exceeded
59	Execution timed out	1067 ms	57028 KB	Time limit exceeded
60	Correct	238 ms	57056 KB	Output is correct
61	Correct	240 ms	57152 KB	Output is correct
62	Correct	221 ms	57156 KB	Output is correct
63	Correct	214 ms	57124 KB	Output is correct
64	Correct	229 ms	56916 KB	Output is correct
65	Execution timed out	1079 ms	56900 KB	Time limit exceeded
66	Execution timed out	1079 ms	56944 KB	Time limit exceeded
67	Execution timed out	1057 ms	57044 KB	Time limit exceeded
68	Execution timed out	1077 ms	56984 KB	Time limit exceeded
69	Execution timed out	1072 ms	57008 KB	Time limit exceeded
70	Execution timed out	1093 ms	45132 KB	Time limit exceeded
71	Execution timed out	1074 ms	57192 KB	Time limit exceeded
72	Execution timed out	1062 ms	57220 KB	Time limit exceeded
73	Execution timed out	1072 ms	57036 KB	Time limit exceeded
74	Execution timed out	1073 ms	57064 KB	Time limit exceeded
75	Execution timed out	1075 ms	57028 KB	Time limit exceeded
76	Execution timed out	1090 ms	56764 KB	Time limit exceeded
77	Execution timed out	1080 ms	56816 KB	Time limit exceeded
78	Execution timed out	1048 ms	56772 KB	Time limit exceeded
79	Execution timed out	1059 ms	56772 KB	Time limit exceeded
80	Execution timed out	1088 ms	56904 KB	Time limit exceeded
81	Execution timed out	1082 ms	57144 KB	Time limit exceeded
82	Execution timed out	1073 ms	57028 KB	Time limit exceeded
83	Execution timed out	1075 ms	57032 KB	Time limit exceeded
84	Execution timed out	1076 ms	57028 KB	Time limit exceeded
85	Execution timed out	1075 ms	57032 KB	Time limit exceeded
86	Execution timed out	1076 ms	57028 KB	Time limit exceeded
87	Execution timed out	1078 ms	57208 KB	Time limit exceeded
88	Execution timed out	1078 ms	57096 KB	Time limit exceeded
89	Execution timed out	1080 ms	57088 KB	Time limit exceeded
90	Execution timed out	1092 ms	45148 KB	Time limit exceeded
91	Execution timed out	1078 ms	57028 KB	Time limit exceeded
92	Execution timed out	1075 ms	57096 KB	Time limit exceeded
93	Execution timed out	1077 ms	57028 KB	Time limit exceeded
94	Execution timed out	1067 ms	57024 KB	Time limit exceeded
95	Execution timed out	1079 ms	57092 KB	Time limit exceeded
96	Execution timed out	1076 ms	57084 KB	Time limit exceeded
97	Execution timed out	1075 ms	57120 KB	Time limit exceeded
98	Execution timed out	1085 ms	57092 KB	Time limit exceeded
99	Execution timed out	1081 ms	57104 KB	Time limit exceeded
100	Execution timed out	1070 ms	57116 KB	Time limit exceeded