oj.uz

Submission #631372

# Submission time Handle Problem Language Result Execution time Memory
631372 2022-08-18T04:04:53 Z CDuong Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 326 ms 79104 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define pii pair<int, int>
using namespace std;
const int mxN = 1e7 + 5;
const int mod = 1e9 + 7;
int m, Q, dp[mxN];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("Bai3.inp", "r", stdin);
    //freopen("Bai3.out", "w", stdout);
    cin >> m >> Q;
    for(int i = 1; i <= m; ++i){
        int p; cin >> p;
        for(int j = p - 1; j < mxN; j += p){
            dp[j] = max(dp[j], p - 1);
        }
    }
    for(int i = mxN - 2; i >= 0; --i){
        dp[i] = max(dp[i], dp[i + 1] - 1);
    }
    dp[0] = 0;
    for(int i = 1; i < mxN; ++i){
        if(dp[i] > 0){
            dp[i] = 1 + dp[i - dp[i]];
        }
        else{
            dp[i] = mod;
        }
    }
    while(Q--){
        int x; cin >> x;
        if(dp[x] >= mxN) cout << "oo" << endl;
        else cout << dp[x] << endl;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 78496 KB Output is correct
2 Correct 124 ms 78588 KB Output is correct
3 Correct 124 ms 78576 KB Output is correct
4 Correct 100 ms 78504 KB Output is correct
5 Correct 111 ms 78492 KB Output is correct
6 Correct 103 ms 78640 KB Output is correct
7 Correct 112 ms 78540 KB Output is correct
8 Correct 123 ms 78576 KB Output is correct
9 Correct 139 ms 78536 KB Output is correct
10 Correct 159 ms 78652 KB Output is correct
11 Correct 151 ms 78576 KB Output is correct
12 Correct 99 ms 78572 KB Output is correct
13 Correct 238 ms 78576 KB Output is correct
14 Correct 266 ms 78564 KB Output is correct
15 Correct 130 ms 78572 KB Output is correct
16 Correct 129 ms 78580 KB Output is correct
17 Correct 127 ms 78584 KB Output is correct
18 Correct 102 ms 78684 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 78480 KB Output is correct
2 Correct 126 ms 78576 KB Output is correct
3 Correct 308 ms 78588 KB Output is correct
4 Correct 136 ms 78576 KB Output is correct
5 Correct 196 ms 78508 KB Output is correct
6 Correct 117 ms 78540 KB Output is correct
7 Correct 122 ms 78580 KB Output is correct
8 Correct 128 ms 78540 KB Output is correct
9 Correct 225 ms 78580 KB Output is correct
10 Correct 285 ms 78580 KB Output is correct
11 Incorrect 267 ms 78580 KB Output isn't correct
12 Correct 165 ms 78580 KB Output is correct
13 Correct 103 ms 78528 KB Output is correct
14 Correct 133 ms 78580 KB Output is correct
15 Correct 232 ms 78580 KB Output is correct
16 Correct 129 ms 78540 KB Output is correct
17 Correct 238 ms 78580 KB Output is correct
18 Correct 240 ms 78668 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 78604 KB Output is correct
2 Correct 288 ms 78708 KB Output is correct
3 Correct 313 ms 78724 KB Output is correct
4 Incorrect 192 ms 78844 KB Output isn't correct
5 Incorrect 155 ms 78700 KB Output isn't correct
6 Correct 246 ms 78860 KB Output is correct
7 Correct 211 ms 78668 KB Output is correct
8 Correct 248 ms 78632 KB Output is correct
9 Correct 244 ms 78576 KB Output is correct
10 Correct 188 ms 78580 KB Output is correct
11 Incorrect 167 ms 78584 KB Output isn't correct
12 Correct 220 ms 78588 KB Output is correct
13 Correct 275 ms 78756 KB Output is correct
14 Correct 180 ms 79104 KB Output is correct
15 Incorrect 242 ms 78580 KB Output isn't correct
16 Correct 254 ms 78576 KB Output is correct
17 Correct 225 ms 78644 KB Output is correct
18 Correct 300 ms 78584 KB Output is correct
19 Incorrect 124 ms 78552 KB Output isn't correct
20 Correct 300 ms 78792 KB Output is correct
21 Incorrect 202 ms 79096 KB Output isn't correct
22 Correct 307 ms 78748 KB Output is correct
23 Correct 153 ms 78744 KB Output is correct
24 Correct 132 ms 78868 KB Output is correct
25 Correct 200 ms 78840 KB Output is correct
26 Incorrect 192 ms 78948 KB Output isn't correct
27 Correct 326 ms 78592 KB Output is correct
28 Incorrect 126 ms 78836 KB Output isn't correct
29 Correct 280 ms 78704 KB Output is correct
30 Correct 324 ms 78708 KB Output is correct
31 Correct 154 ms 78704 KB Output is correct
32 Incorrect 171 ms 78752 KB Output isn't correct
33 Incorrect 123 ms 78728 KB Output isn't correct
34 Correct 210 ms 78664 KB Output is correct
35 Incorrect 130 ms 78796 KB Output isn't correct
36 Correct 316 ms 78704 KB Output is correct
37 Incorrect 150 ms 78700 KB Output isn't correct
38 Correct 244 ms 78832 KB Output is correct
39 Incorrect 139 ms 78856 KB Output isn't correct
40 Correct 224 ms 78836 KB Output is correct
41 Correct 196 ms 78576 KB Output is correct
42 Correct 281 ms 78964 KB Output is correct