oj.uz

Submission #1037226

# Submission time Handle Problem Language Result Execution time Memory
1037226 2024-07-28T11:06:16 Z Alfraganus Bomb (IZhO17_bomb) C++17
29 / 100
 1000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 1e9 + 7;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char> (m));
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> a[i][j];
    if(n <= 40 and m <= 40){
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                vector<vector<char>> b = a;
                for(int i1 = 0; i1 <= n - i; i1 ++){
                    for(int i2 = 0; i2 <= m - j; i2 ++){
                        if(b[i1][i2] != '0'){
                            bool flag = 1;
                            for(int x = 0; x < i; x ++){
                                for(int y = 0; y < j; y ++){
                                    if(b[i1 + x][i2 + y] == '0')
                                        flag = false;
                                }
                            }
                            if(flag){
                                for(int x = 0; x < i; x ++){
                                    for(int y = 0; y < j; y ++){
                                        b[i1 + x][i2 + y] = '2';
                                    }
                                }
                            }
                        }
                    }
                }
                int cnt = 0;
                for(int i = 0; i < n; i ++){
                    for(int j = 0; j < m; j ++){
                        cnt += b[i][j] == '1';
                    }
                }
                if(cnt == 0)
                    ans = max(ans, i * j);
            }
        }
        cout << ans;
        return;
    }
    vector<vector<int>> pref(n + 1, vector<int> (m + 1));
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + (a[i][j] == '0');
    vector<vector<array<int, 2>>> dp(n, vector<array<int, 2>> (m, {0, 0}));
    int ans = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            bool flag = 1;
            for(int x = 0; x < n; x ++){
                for(int y = 0; y < m; y ++){
                    if(x + i <= n and y + j <= m and pref[x + i][y + j] - pref[x + i][y] - pref[x][y + j] + pref[x][y] == 0)
                        dp[x][y] = {i, j};
                    else{
                        dp[x][y] = {0, 0};
                        if(y > 0 and dp[x][y - 1][1] > 1)
                            dp[x][y] = {dp[x][y - 1][0], dp[x][y - 1][1] - 1};
                        else if(x > 0 and dp[x - 1][y][0] > 1)
                            dp[x][y] = {dp[x - 1][y][0] - 1, dp[x - 1][y][1]};
                    }
                    if(a[x][y] == '1' and dp[x][y][0] == 0 and dp[x][y][1] == 0){
                        flag = 0;
                        break;
                    }
                }
                if(!flag)
                    break;
            }
            if(flag)
                ans = max(ans, i * j);
            else
                break;
        }
    }
    cout << ans;
}

signed main()
{
    fastio;
    #ifdef Javohir
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Subtask #1
29.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Incorrect 1 ms 604 KB Output isn't correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Incorrect 2 ms 604 KB Output isn't correct
24 Incorrect 1 ms 604 KB Output isn't correct
25 Incorrect 2 ms 604 KB Output isn't correct
26 Correct 3 ms 604 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 12 ms 3164 KB Output is correct
29 Incorrect 74 ms 3540 KB Output isn't correct
30 Incorrect 110 ms 5084 KB Output isn't correct
31 Incorrect 87 ms 4164 KB Output isn't correct
32 Incorrect 79 ms 4188 KB Output isn't correct
33 Incorrect 182 ms 5464 KB Output isn't correct
34 Correct 14 ms 2392 KB Output is correct
35 Incorrect 114 ms 5460 KB Output isn't correct
36 Correct 458 ms 5468 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Runtime error 114 ms 131072 KB Execution killed with signal 9
39 Correct 1 ms 344 KB Output is correct
40 Execution timed out 1079 ms 19292 KB Time limit exceeded
41 Correct 1 ms 344 KB Output is correct
42 Correct 28 ms 604 KB Output is correct
43 Runtime error 112 ms 131072 KB Execution killed with signal 9
44 Execution timed out 1051 ms 5468 KB Time limit exceeded
45 Runtime error 116 ms 131072 KB Execution killed with signal 9
46 Runtime error 113 ms 131072 KB Execution killed with signal 9
47 Runtime error 115 ms 131072 KB Execution killed with signal 9
48 Runtime error 115 ms 131072 KB Execution killed with signal 9
49 Runtime error 113 ms 131072 KB Execution killed with signal 9
50 Runtime error 115 ms 131072 KB Execution killed with signal 9
51 Runtime error 116 ms 131072 KB Execution killed with signal 9
52 Runtime error 113 ms 131072 KB Execution killed with signal 9
53 Runtime error 121 ms 131072 KB Execution killed with signal 9
54 Runtime error 111 ms 131072 KB Execution killed with signal 9
55 Runtime error 116 ms 131072 KB Execution killed with signal 9
56 Runtime error 115 ms 131072 KB Execution killed with signal 9
57 Runtime error 118 ms 131072 KB Execution killed with signal 9
58 Runtime error 114 ms 131072 KB Execution killed with signal 9
59 Runtime error 116 ms 131072 KB Execution killed with signal 9
60 Runtime error 114 ms 131072 KB Execution killed with signal 9
61 Runtime error 127 ms 131072 KB Execution killed with signal 9
62 Runtime error 117 ms 131072 KB Execution killed with signal 9
63 Runtime error 116 ms 131072 KB Execution killed with signal 9
64 Runtime error 122 ms 131072 KB Execution killed with signal 9
65 Runtime error 118 ms 131072 KB Execution killed with signal 9
66 Runtime error 121 ms 131072 KB Execution killed with signal 9
67 Runtime error 116 ms 131072 KB Execution killed with signal 9
68 Runtime error 120 ms 131072 KB Execution killed with signal 9
69 Runtime error 124 ms 131072 KB Execution killed with signal 9
70 Execution timed out 1097 ms 98380 KB Time limit exceeded
71 Runtime error 113 ms 131072 KB Execution killed with signal 9
72 Runtime error 120 ms 131072 KB Execution killed with signal 9
73 Runtime error 117 ms 131072 KB Execution killed with signal 9
74 Runtime error 126 ms 131072 KB Execution killed with signal 9
75 Runtime error 123 ms 131072 KB Execution killed with signal 9
76 Runtime error 126 ms 131072 KB Execution killed with signal 9
77 Runtime error 112 ms 131072 KB Execution killed with signal 9
78 Runtime error 115 ms 131072 KB Execution killed with signal 9
79 Runtime error 123 ms 131072 KB Execution killed with signal 9
80 Runtime error 114 ms 131072 KB Execution killed with signal 9
81 Runtime error 116 ms 131072 KB Execution killed with signal 9
82 Runtime error 114 ms 131072 KB Execution killed with signal 9
83 Runtime error 122 ms 131072 KB Execution killed with signal 9
84 Runtime error 114 ms 131072 KB Execution killed with signal 9
85 Runtime error 115 ms 131072 KB Execution killed with signal 9
86 Runtime error 120 ms 131072 KB Execution killed with signal 9
87 Runtime error 118 ms 131072 KB Execution killed with signal 9
88 Runtime error 124 ms 131072 KB Execution killed with signal 9
89 Runtime error 136 ms 131072 KB Execution killed with signal 9
90 Execution timed out 1033 ms 98560 KB Time limit exceeded
91 Runtime error 118 ms 131072 KB Execution killed with signal 9
92 Runtime error 120 ms 131072 KB Execution killed with signal 9
93 Runtime error 122 ms 131072 KB Execution killed with signal 9
94 Runtime error 127 ms 131072 KB Execution killed with signal 9
95 Runtime error 117 ms 131072 KB Execution killed with signal 9
96 Runtime error 115 ms 131072 KB Execution killed with signal 9
97 Runtime error 147 ms 131072 KB Execution killed with signal 9
98 Runtime error 122 ms 131072 KB Execution killed with signal 9
99 Runtime error 118 ms 131072 KB Execution killed with signal 9
100 Runtime error 117 ms 131072 KB Execution killed with signal 9