oj.uz

Submission #1037224

# Submission time Handle Problem Language Result Execution time Memory
1037224 2024-07-28T11:05:13 Z Alfraganus Bomb (IZhO17_bomb) C++17
28 / 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];
    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
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 Incorrect 0 ms 348 KB Output isn't 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 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 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 11 ms 3224 KB Output is correct
29 Incorrect 81 ms 3548 KB Output isn't correct
30 Incorrect 119 ms 5080 KB Output isn't correct
31 Incorrect 86 ms 4184 KB Output isn't correct
32 Incorrect 82 ms 4188 KB Output isn't correct
33 Incorrect 198 ms 5212 KB Output isn't correct
34 Correct 15 ms 2648 KB Output is correct
35 Incorrect 112 ms 5468 KB Output isn't correct
36 Correct 496 ms 5464 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Runtime error 136 ms 131072 KB Execution killed with signal 9
39 Correct 1 ms 344 KB Output is correct
40 Execution timed out 1095 ms 19292 KB Time limit exceeded
41 Correct 0 ms 344 KB Output is correct
42 Correct 28 ms 604 KB Output is correct
43 Runtime error 139 ms 131072 KB Execution killed with signal 9
44 Execution timed out 1070 ms 5468 KB Time limit exceeded
45 Runtime error 122 ms 131072 KB Execution killed with signal 9
46 Runtime error 121 ms 131072 KB Execution killed with signal 9
47 Runtime error 129 ms 131072 KB Execution killed with signal 9
48 Runtime error 125 ms 131072 KB Execution killed with signal 9
49 Runtime error 121 ms 131072 KB Execution killed with signal 9
50 Runtime error 119 ms 131072 KB Execution killed with signal 9
51 Runtime error 123 ms 131072 KB Execution killed with signal 9
52 Runtime error 121 ms 131072 KB Execution killed with signal 9
53 Runtime error 115 ms 131072 KB Execution killed with signal 9
54 Runtime error 113 ms 131072 KB Execution killed with signal 9
55 Runtime error 115 ms 131072 KB Execution killed with signal 9
56 Runtime error 125 ms 131072 KB Execution killed with signal 9
57 Runtime error 158 ms 131072 KB Execution killed with signal 9
58 Runtime error 159 ms 131072 KB Execution killed with signal 9
59 Runtime error 120 ms 131072 KB Execution killed with signal 9
60 Runtime error 120 ms 131072 KB Execution killed with signal 9
61 Runtime error 114 ms 131072 KB Execution killed with signal 9
62 Runtime error 124 ms 131072 KB Execution killed with signal 9
63 Runtime error 130 ms 131072 KB Execution killed with signal 9
64 Runtime error 116 ms 131072 KB Execution killed with signal 9
65 Runtime error 115 ms 131072 KB Execution killed with signal 9
66 Runtime error 120 ms 131072 KB Execution killed with signal 9
67 Runtime error 133 ms 131072 KB Execution killed with signal 9
68 Runtime error 114 ms 131072 KB Execution killed with signal 9
69 Runtime error 119 ms 131072 KB Execution killed with signal 9
70 Execution timed out 1074 ms 98384 KB Time limit exceeded
71 Runtime error 121 ms 131072 KB Execution killed with signal 9
72 Runtime error 116 ms 131072 KB Execution killed with signal 9
73 Runtime error 114 ms 131072 KB Execution killed with signal 9
74 Runtime error 124 ms 131072 KB Execution killed with signal 9
75 Runtime error 125 ms 131072 KB Execution killed with signal 9
76 Runtime error 114 ms 131072 KB Execution killed with signal 9
77 Runtime error 112 ms 131072 KB Execution killed with signal 9
78 Runtime error 125 ms 131072 KB Execution killed with signal 9
79 Runtime error 115 ms 131072 KB Execution killed with signal 9
80 Runtime error 125 ms 131072 KB Execution killed with signal 9
81 Runtime error 110 ms 131072 KB Execution killed with signal 9
82 Runtime error 120 ms 131072 KB Execution killed with signal 9
83 Runtime error 117 ms 131072 KB Execution killed with signal 9
84 Runtime error 111 ms 131072 KB Execution killed with signal 9
85 Runtime error 113 ms 131072 KB Execution killed with signal 9
86 Runtime error 115 ms 131072 KB Execution killed with signal 9
87 Runtime error 115 ms 131072 KB Execution killed with signal 9
88 Runtime error 114 ms 131072 KB Execution killed with signal 9
89 Runtime error 111 ms 131072 KB Execution killed with signal 9
90 Execution timed out 1047 ms 98380 KB Time limit exceeded
91 Runtime error 118 ms 131072 KB Execution killed with signal 9
92 Runtime error 115 ms 131072 KB Execution killed with signal 9
93 Runtime error 114 ms 131072 KB Execution killed with signal 9
94 Runtime error 116 ms 131072 KB Execution killed with signal 9
95 Runtime error 116 ms 131072 KB Execution killed with signal 9
96 Runtime error 116 ms 131072 KB Execution killed with signal 9
97 Runtime error 114 ms 131072 KB Execution killed with signal 9
98 Runtime error 119 ms 131072 KB Execution killed with signal 9
99 Runtime error 112 ms 131072 KB Execution killed with signal 9
100 Runtime error 121 ms 131072 KB Execution killed with signal 9