oj.uz

Submission #1037211

# Submission time Handle Problem Language Result Execution time Memory
1037211 2024-07-28T10:47:10 Z Alfraganus Bomb (IZhO17_bomb) C++17
27 / 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);
            }
        }
    }
    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
27.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 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 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 0 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 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 472 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Incorrect 3 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 7 ms 720 KB Output isn't correct
24 Incorrect 2 ms 604 KB Output isn't correct
25 Incorrect 13 ms 604 KB Output isn't correct
26 Correct 6 ms 728 KB Output is correct
27 Correct 3 ms 2396 KB Output is correct
28 Correct 15 ms 3164 KB Output is correct
29 Execution timed out 1002 ms 3676 KB Time limit exceeded
30 Execution timed out 1053 ms 5212 KB Time limit exceeded
31 Incorrect 924 ms 4188 KB Output isn't correct
32 Incorrect 870 ms 4468 KB Output isn't correct
33 Execution timed out 1077 ms 5468 KB Time limit exceeded
34 Correct 46 ms 2396 KB Output is correct
35 Incorrect 277 ms 5468 KB Output isn't correct
36 Execution timed out 1041 ms 5464 KB Time limit exceeded
37 Correct 1 ms 348 KB Output is correct
38 Runtime error 103 ms 131072 KB Execution killed with signal 9
39 Correct 0 ms 344 KB Output is correct
40 Execution timed out 1097 ms 20128 KB Time limit exceeded
41 Correct 0 ms 348 KB Output is correct
42 Correct 35 ms 604 KB Output is correct
43 Runtime error 104 ms 131072 KB Execution killed with signal 9
44 Execution timed out 1089 ms 5720 KB Time limit exceeded
45 Runtime error 111 ms 131072 KB Execution killed with signal 9
46 Runtime error 139 ms 131072 KB Execution killed with signal 9
47 Runtime error 107 ms 131072 KB Execution killed with signal 9
48 Runtime error 107 ms 131072 KB Execution killed with signal 9
49 Runtime error 117 ms 131072 KB Execution killed with signal 9
50 Runtime error 104 ms 131072 KB Execution killed with signal 9
51 Runtime error 104 ms 131072 KB Execution killed with signal 9
52 Runtime error 130 ms 131072 KB Execution killed with signal 9
53 Runtime error 121 ms 131072 KB Execution killed with signal 9
54 Runtime error 141 ms 131072 KB Execution killed with signal 9
55 Runtime error 102 ms 131072 KB Execution killed with signal 9
56 Runtime error 103 ms 131072 KB Execution killed with signal 9
57 Runtime error 117 ms 131072 KB Execution killed with signal 9
58 Runtime error 112 ms 131072 KB Execution killed with signal 9
59 Runtime error 110 ms 131072 KB Execution killed with signal 9
60 Runtime error 152 ms 131072 KB Execution killed with signal 9
61 Runtime error 103 ms 131072 KB Execution killed with signal 9
62 Runtime error 115 ms 131072 KB Execution killed with signal 9
63 Runtime error 108 ms 131072 KB Execution killed with signal 9
64 Runtime error 113 ms 131072 KB Execution killed with signal 9
65 Runtime error 105 ms 131072 KB Execution killed with signal 9
66 Runtime error 129 ms 131072 KB Execution killed with signal 9
67 Runtime error 108 ms 131072 KB Execution killed with signal 9
68 Runtime error 108 ms 131072 KB Execution killed with signal 9
69 Runtime error 145 ms 131072 KB Execution killed with signal 9
70 Execution timed out 1065 ms 102348 KB Time limit exceeded
71 Runtime error 111 ms 131072 KB Execution killed with signal 9
72 Runtime error 105 ms 131072 KB Execution killed with signal 9
73 Runtime error 104 ms 131072 KB Execution killed with signal 9
74 Runtime error 104 ms 131072 KB Execution killed with signal 9
75 Runtime error 108 ms 131072 KB Execution killed with signal 9
76 Runtime error 119 ms 131072 KB Execution killed with signal 9
77 Runtime error 132 ms 131072 KB Execution killed with signal 9
78 Runtime error 107 ms 131072 KB Execution killed with signal 9
79 Runtime error 123 ms 131072 KB Execution killed with signal 9
80 Runtime error 143 ms 131072 KB Execution killed with signal 9
81 Runtime error 104 ms 131072 KB Execution killed with signal 9
82 Runtime error 117 ms 131072 KB Execution killed with signal 9
83 Runtime error 109 ms 131072 KB Execution killed with signal 9
84 Runtime error 105 ms 131072 KB Execution killed with signal 9
85 Runtime error 105 ms 131072 KB Execution killed with signal 9
86 Runtime error 129 ms 131072 KB Execution killed with signal 9
87 Runtime error 111 ms 131072 KB Execution killed with signal 9
88 Runtime error 113 ms 131072 KB Execution killed with signal 9
89 Runtime error 104 ms 131072 KB Execution killed with signal 9
90 Execution timed out 1055 ms 102484 KB Time limit exceeded
91 Runtime error 112 ms 131072 KB Execution killed with signal 9
92 Runtime error 107 ms 131072 KB Execution killed with signal 9
93 Runtime error 108 ms 131072 KB Execution killed with signal 9
94 Runtime error 104 ms 131072 KB Execution killed with signal 9
95 Runtime error 120 ms 131072 KB Execution killed with signal 9
96 Runtime error 115 ms 131072 KB Execution killed with signal 9
97 Runtime error 133 ms 131072 KB Execution killed with signal 9
98 Runtime error 105 ms 131072 KB Execution killed with signal 9
99 Runtime error 137 ms 131072 KB Execution killed with signal 9
100 Runtime error 114 ms 131072 KB Execution killed with signal 9