oj.uz

Submission #1109931

# Submission time Handle Problem Language Result Execution time Memory
1109931 2024-11-08T06:41:43 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 165 ms 158680 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 1e7 +10, inf = INT_MAX, LG = 20;
int dp[sze],ff[sze];
void fast(){
    int n,q;
    cin>>n>>q;
    int mx = 0;
    for(int i =1;i<=n;i++){
        int p;
        cin>>p;
        mx=max(mx,p);
        for(int u = p;u<sze;u+=p){
            ff[u-1]= (p-1); 
        }
        ff[sze-1]=max(ff[sze-1],(sze-1)%p); 
    }
    for(int i = sze-1;i>=1;i--){
        ff[i]=max(ff[i],ff[i+1]-1);
    }
    for(int i=1;i<sze;i++){
        if(i<mx){
            dp[i]=1;
            continue;
        }
        dp[i]=inf;
        dp[i]=min(dp[i],dp[i - ff[i]] +1);
    }
 
    while(q--){
        int v;
        cin>>v;
        if(dp[v]>=inf){
            cout<<"oo"<<endl;
        }
        else{
            cout<<dp[v]<<endl;
        }
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 157000 KB Output is correct
2 Correct 67 ms 156956 KB Output is correct
3 Correct 63 ms 156960 KB Output is correct
4 Correct 54 ms 157000 KB Output is correct
5 Correct 61 ms 157000 KB Output is correct
6 Correct 69 ms 157000 KB Output is correct
7 Correct 66 ms 157000 KB Output is correct
8 Correct 67 ms 157000 KB Output is correct
9 Correct 78 ms 157000 KB Output is correct
10 Correct 90 ms 157000 KB Output is correct
11 Correct 85 ms 156964 KB Output is correct
12 Correct 62 ms 157000 KB Output is correct
13 Correct 114 ms 157000 KB Output is correct
14 Correct 122 ms 156844 KB Output is correct
15 Correct 72 ms 156964 KB Output is correct
16 Correct 73 ms 157000 KB Output is correct
17 Correct 73 ms 157008 KB Output is correct
18 Correct 66 ms 157000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 157000 KB Output is correct
2 Correct 79 ms 157492 KB Output is correct
3 Correct 137 ms 157224 KB Output is correct
4 Correct 70 ms 157000 KB Output is correct
5 Correct 117 ms 157224 KB Output is correct
6 Correct 63 ms 156992 KB Output is correct
7 Correct 59 ms 157000 KB Output is correct
8 Correct 65 ms 157000 KB Output is correct
9 Correct 117 ms 157000 KB Output is correct
10 Correct 140 ms 157256 KB Output is correct
11 Correct 123 ms 157276 KB Output is correct
12 Correct 93 ms 156972 KB Output is correct
13 Correct 67 ms 157000 KB Output is correct
14 Correct 68 ms 157000 KB Output is correct
15 Correct 116 ms 157256 KB Output is correct
16 Correct 71 ms 157512 KB Output is correct
17 Correct 110 ms 157000 KB Output is correct
18 Correct 121 ms 157512 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 157744 KB Output is correct
2 Correct 148 ms 157400 KB Output is correct
3 Correct 147 ms 157748 KB Output is correct
4 Correct 113 ms 157768 KB Output is correct
5 Correct 99 ms 158280 KB Output is correct
6 Correct 135 ms 158024 KB Output is correct
7 Correct 119 ms 158024 KB Output is correct
8 Correct 134 ms 157524 KB Output is correct
9 Correct 128 ms 157744 KB Output is correct
10 Correct 110 ms 156920 KB Output is correct
11 Correct 90 ms 157220 KB Output is correct
12 Correct 116 ms 157256 KB Output is correct
13 Correct 138 ms 158024 KB Output is correct
14 Correct 97 ms 158248 KB Output is correct
15 Correct 112 ms 157256 KB Output is correct
16 Correct 122 ms 157256 KB Output is correct
17 Correct 108 ms 157256 KB Output is correct
18 Correct 137 ms 157456 KB Output is correct
19 Correct 74 ms 157012 KB Output is correct
20 Correct 137 ms 157836 KB Output is correct
21 Correct 103 ms 158280 KB Output is correct
22 Correct 157 ms 158536 KB Output is correct
23 Correct 87 ms 158096 KB Output is correct
24 Correct 88 ms 157516 KB Output is correct
25 Correct 112 ms 157996 KB Output is correct
26 Correct 106 ms 157768 KB Output is correct
27 Correct 148 ms 157988 KB Output is correct
28 Correct 69 ms 158024 KB Output is correct
29 Correct 155 ms 158680 KB Output is correct
30 Correct 131 ms 158280 KB Output is correct
31 Correct 77 ms 157768 KB Output is correct
32 Correct 93 ms 157512 KB Output is correct
33 Correct 78 ms 157768 KB Output is correct
34 Correct 109 ms 158028 KB Output is correct
35 Correct 77 ms 157768 KB Output is correct
36 Correct 165 ms 158544 KB Output is correct
37 Correct 100 ms 158208 KB Output is correct
38 Correct 122 ms 158032 KB Output is correct
39 Correct 88 ms 158024 KB Output is correct
40 Correct 118 ms 158024 KB Output is correct
41 Correct 99 ms 158032 KB Output is correct
42 Correct 152 ms 158176 KB Output is correct