oj.uz

답안 #1037229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037229 2024-07-28T11:10:59 Z Alfraganus Bomb (IZhO17_bomb) C++17
39 / 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};
                        if(x > 0 and dp[x - 1][y][0] > 1)
                            dp[x][y] = max(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
39.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is 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 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 9 ms 712 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 5 ms 856 KB Output is correct
26 Correct 4 ms 604 KB Output is correct
27 Correct 2 ms 2436 KB Output is correct
28 Correct 15 ms 3160 KB Output is correct
29 Execution timed out 1100 ms 3420 KB Time limit exceeded
30 Correct 263 ms 5084 KB Output is correct
31 Correct 260 ms 3932 KB Output is correct
32 Correct 162 ms 4184 KB Output is correct
33 Correct 966 ms 5468 KB Output is correct
34 Correct 19 ms 2396 KB Output is correct
35 Correct 181 ms 5468 KB Output is correct
36 Correct 686 ms 5464 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Runtime error 116 ms 131072 KB Execution killed with signal 9
39 Correct 0 ms 348 KB Output is correct
40 Execution timed out 1101 ms 19292 KB Time limit exceeded
41 Correct 0 ms 344 KB Output is correct
42 Correct 58 ms 600 KB Output is correct
43 Runtime error 112 ms 131072 KB Execution killed with signal 9
44 Execution timed out 1069 ms 5468 KB Time limit exceeded
45 Runtime error 111 ms 131072 KB Execution killed with signal 9
46 Runtime error 117 ms 131072 KB Execution killed with signal 9
47 Runtime error 120 ms 131072 KB Execution killed with signal 9
48 Runtime error 112 ms 131072 KB Execution killed with signal 9
49 Runtime error 115 ms 131072 KB Execution killed with signal 9
50 Runtime error 122 ms 131072 KB Execution killed with signal 9
51 Runtime error 119 ms 131072 KB Execution killed with signal 9
52 Runtime error 114 ms 131072 KB Execution killed with signal 9
53 Runtime error 111 ms 131072 KB Execution killed with signal 9
54 Runtime error 122 ms 131072 KB Execution killed with signal 9
55 Runtime error 114 ms 131072 KB Execution killed with signal 9
56 Runtime error 111 ms 131072 KB Execution killed with signal 9
57 Runtime error 112 ms 131072 KB Execution killed with signal 9
58 Runtime error 119 ms 131072 KB Execution killed with signal 9
59 Runtime error 113 ms 131072 KB Execution killed with signal 9
60 Runtime error 113 ms 131072 KB Execution killed with signal 9
61 Runtime error 112 ms 131072 KB Execution killed with signal 9
62 Runtime error 117 ms 131072 KB Execution killed with signal 9
63 Runtime error 113 ms 131072 KB Execution killed with signal 9
64 Runtime error 117 ms 131072 KB Execution killed with signal 9
65 Runtime error 135 ms 131072 KB Execution killed with signal 9
66 Runtime error 138 ms 131072 KB Execution killed with signal 9
67 Runtime error 111 ms 131072 KB Execution killed with signal 9
68 Runtime error 112 ms 131072 KB Execution killed with signal 9
69 Runtime error 111 ms 131072 KB Execution killed with signal 9
70 Execution timed out 1079 ms 98384 KB Time limit exceeded
71 Runtime error 121 ms 131072 KB Execution killed with signal 9
72 Runtime error 114 ms 131072 KB Execution killed with signal 9
73 Runtime error 123 ms 131072 KB Execution killed with signal 9
74 Runtime error 135 ms 131072 KB Execution killed with signal 9
75 Runtime error 128 ms 131072 KB Execution killed with signal 9
76 Runtime error 112 ms 131072 KB Execution killed with signal 9
77 Runtime error 124 ms 131072 KB Execution killed with signal 9
78 Runtime error 121 ms 131072 KB Execution killed with signal 9
79 Runtime error 118 ms 131072 KB Execution killed with signal 9
80 Runtime error 120 ms 131072 KB Execution killed with signal 9
81 Runtime error 113 ms 131072 KB Execution killed with signal 9
82 Runtime error 116 ms 131072 KB Execution killed with signal 9
83 Runtime error 111 ms 131072 KB Execution killed with signal 9
84 Runtime error 113 ms 131072 KB Execution killed with signal 9
85 Runtime error 112 ms 131072 KB Execution killed with signal 9
86 Runtime error 116 ms 131072 KB Execution killed with signal 9
87 Runtime error 112 ms 131072 KB Execution killed with signal 9
88 Runtime error 118 ms 131072 KB Execution killed with signal 9
89 Runtime error 111 ms 131072 KB Execution killed with signal 9
90 Execution timed out 1091 ms 98556 KB Time limit exceeded
91 Runtime error 114 ms 131072 KB Execution killed with signal 9
92 Runtime error 120 ms 131072 KB Execution killed with signal 9
93 Runtime error 113 ms 131072 KB Execution killed with signal 9
94 Runtime error 113 ms 131072 KB Execution killed with signal 9
95 Runtime error 116 ms 131072 KB Execution killed with signal 9
96 Runtime error 121 ms 131072 KB Execution killed with signal 9
97 Runtime error 111 ms 131072 KB Execution killed with signal 9
98 Runtime error 116 ms 131072 KB Execution killed with signal 9
99 Runtime error 119 ms 131072 KB Execution killed with signal 9
100 Runtime error 118 ms 131072 KB Execution killed with signal 9