oj.uz

Submission #764232

# Submission time Handle Problem Language Result Execution time Memory
764232 2023-06-23T09:05:54 Z someone Bomb (IZhO17_bomb) C++14
20 / 100
 218 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2542, INF = 1e18 + 42;

vector<pair<int, int>> pos[N];
int n, m, val[N][N], occ[N], sz[N][N];

int F(int lig, int col) {
    if(sz[lig][col] < 0)
        return lig * m + col;
    return sz[lig][col] = F(sz[lig][col] / m, sz[lig][col] % m);
}

void U(int l1, int c1, int l2, int c2) {
    int a = F(l1, c1), b = F(l2, c2);
    if(a == b) return;
    occ[-sz[a / m][a % m]]--;
    occ[-sz[b / m][b % m]]--;
    sz[a / m][a % m] += sz[b / m][b % m];
    sz[b / m][b % m] = a;
    occ[-sz[a / m][a % m]]++;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            char c; cin >> c;
            val[i][j] = (int)(c - '0');
            sz[i][j] = -INF;
        }
    for(int i = 0; i < n; i++)
        for(int j = 1; j < m; j++)
            if(val[i][j] == 1)
                val[i][j] += val[i][j-1];

    int bound = INF;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            if(val[i][j] > 0 && val[i][j+1] == 0)
                bound = min(bound, val[i][j]);
            pos[val[i][j]].push_back({i, j});
        }
    if(bound == INF) {
        cout << "0\n";
        return 0;
    }

    int ans = 0;
    for(int i = N-1; i > 0; i--) {
        for(auto pii : pos[i]) {
            occ[1]++;
            int lig = pii.first,
                col = pii.second;
            sz[lig][col] = -1;
            if(0 < lig && val[lig-1][col] >= i && sz[lig-1][col] != -INF)
                U(lig, col, lig-1, col);
            if(lig < n-1 && val[lig+1][col] >= i && sz[lig+1][col] != -INF)
                U(lig, col, lig+1, col);
        }
        if(i <= bound) {
            int mini = 0;
            for(int j = N-1; j > 0; j--)
                if(occ[j])
                    mini = j;
            ans = max(ans, mini * i);
        }
    }
    cout << ans << '\n';
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 11 ms 20692 KB Output is correct
4 Correct 9 ms 20708 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 468 KB Output isn't correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Correct 1 ms 524 KB Output is correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Correct 1 ms 516 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 520 KB Output is correct
15 Incorrect 1 ms 496 KB Output isn't correct
16 Correct 1 ms 468 KB Output is correct
17 Incorrect 1 ms 1108 KB Output isn't correct
18 Correct 1 ms 1236 KB Output is correct
19 Incorrect 1 ms 1492 KB Output isn't correct
20 Incorrect 1 ms 1492 KB Output isn't correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 1 ms 1316 KB Output is correct
23 Incorrect 2 ms 1548 KB Output isn't correct
24 Incorrect 1 ms 1364 KB Output isn't correct
25 Incorrect 1 ms 1620 KB Output isn't correct
26 Correct 2 ms 1552 KB Output is correct
27 Correct 6 ms 5908 KB Output is correct
28 Correct 5 ms 6740 KB Output is correct
29 Correct 8 ms 8336 KB Output is correct
30 Incorrect 11 ms 12240 KB Output isn't correct
31 Incorrect 10 ms 8076 KB Output isn't correct
32 Incorrect 12 ms 10896 KB Output isn't correct
33 Incorrect 10 ms 12628 KB Output isn't correct
34 Correct 4 ms 6752 KB Output is correct
35 Incorrect 9 ms 11708 KB Output isn't correct
36 Incorrect 14 ms 10964 KB Output isn't correct
37 Incorrect 1 ms 468 KB Output isn't correct
38 Runtime error 206 ms 131072 KB Execution killed with signal 9
39 Incorrect 1 ms 520 KB Output isn't correct
40 Incorrect 68 ms 37196 KB Output isn't correct
41 Incorrect 1 ms 468 KB Output isn't correct
42 Incorrect 2 ms 1556 KB Output isn't correct
43 Runtime error 154 ms 131072 KB Execution killed with signal 9
44 Incorrect 17 ms 11720 KB Output isn't correct
45 Runtime error 131 ms 131072 KB Execution killed with signal 9
46 Runtime error 133 ms 131072 KB Execution killed with signal 9
47 Runtime error 134 ms 131072 KB Execution killed with signal 9
48 Runtime error 134 ms 131072 KB Execution killed with signal 9
49 Runtime error 136 ms 131072 KB Execution killed with signal 9
50 Runtime error 132 ms 131072 KB Execution killed with signal 9
51 Runtime error 145 ms 131072 KB Execution killed with signal 9
52 Runtime error 150 ms 131072 KB Execution killed with signal 9
53 Runtime error 159 ms 131072 KB Execution killed with signal 9
54 Runtime error 140 ms 131072 KB Execution killed with signal 9
55 Runtime error 143 ms 131072 KB Execution killed with signal 9
56 Runtime error 149 ms 131072 KB Execution killed with signal 9
57 Runtime error 214 ms 131072 KB Execution killed with signal 9
58 Runtime error 153 ms 131072 KB Execution killed with signal 9
59 Runtime error 159 ms 131072 KB Execution killed with signal 9
60 Runtime error 132 ms 131072 KB Execution killed with signal 9
61 Runtime error 161 ms 131072 KB Execution killed with signal 9
62 Runtime error 147 ms 131072 KB Execution killed with signal 9
63 Runtime error 144 ms 131072 KB Execution killed with signal 9
64 Runtime error 142 ms 131072 KB Execution killed with signal 9
65 Runtime error 218 ms 131072 KB Execution killed with signal 9
66 Runtime error 137 ms 131072 KB Execution killed with signal 9
67 Runtime error 133 ms 131072 KB Execution killed with signal 9
68 Runtime error 136 ms 131072 KB Execution killed with signal 9
69 Runtime error 151 ms 131072 KB Execution killed with signal 9
70 Runtime error 142 ms 131072 KB Execution killed with signal 9
71 Runtime error 130 ms 131072 KB Execution killed with signal 9
72 Runtime error 149 ms 131072 KB Execution killed with signal 9
73 Runtime error 139 ms 131072 KB Execution killed with signal 9
74 Runtime error 137 ms 131072 KB Execution killed with signal 9
75 Runtime error 139 ms 131072 KB Execution killed with signal 9
76 Runtime error 149 ms 131072 KB Execution killed with signal 9
77 Runtime error 145 ms 131072 KB Execution killed with signal 9
78 Runtime error 139 ms 131072 KB Execution killed with signal 9
79 Runtime error 141 ms 131072 KB Execution killed with signal 9
80 Runtime error 130 ms 131072 KB Execution killed with signal 9
81 Runtime error 140 ms 131072 KB Execution killed with signal 9
82 Runtime error 136 ms 131072 KB Execution killed with signal 9
83 Runtime error 133 ms 131072 KB Execution killed with signal 9
84 Runtime error 133 ms 131072 KB Execution killed with signal 9
85 Runtime error 132 ms 131072 KB Execution killed with signal 9
86 Runtime error 148 ms 131072 KB Execution killed with signal 9
87 Runtime error 137 ms 131072 KB Execution killed with signal 9
88 Runtime error 146 ms 131072 KB Execution killed with signal 9
89 Runtime error 147 ms 131072 KB Execution killed with signal 9
90 Runtime error 132 ms 131072 KB Execution killed with signal 9
91 Runtime error 136 ms 131072 KB Execution killed with signal 9
92 Runtime error 140 ms 131072 KB Execution killed with signal 9
93 Runtime error 167 ms 131072 KB Execution killed with signal 9
94 Runtime error 140 ms 131072 KB Execution killed with signal 9
95 Runtime error 153 ms 131072 KB Execution killed with signal 9
96 Runtime error 136 ms 131072 KB Execution killed with signal 9
97 Runtime error 144 ms 131072 KB Execution killed with signal 9
98 Runtime error 142 ms 131072 KB Execution killed with signal 9
99 Runtime error 155 ms 131072 KB Execution killed with signal 9
100 Runtime error 146 ms 131072 KB Execution killed with signal 9