oj.uz

Submission #1109615

# Submission time Handle Problem Language Result Execution time Memory
1109615 2024-11-07T07:16:57 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 117 ms 15684 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 = 1e5 +10, inf = INT_MAX, LG = 20;
int dp[sze];
void fast(){
    int n,q;
    cin>>n>>q;
    multiset<int> ans; 
    int mx = 0;
    multiset<pair<int,int>> ev;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        // event[p].pb(p);
        ev.ins({p,p});
        mx=max(mx,p);
    }
    vector<int> primus;
    for(int i =1;i<sze;i++){
        dp[i]=inf;
        primus.clear();
        while(!ev.empty()){
            auto beg = *ev.begin();
            if(beg.first != i){
                break;
            }
            ev.erase(ev.begin());
            primus.pb(beg.second);
            if(i != beg.second){
                ans.erase(ans.find(dp[i - beg.second]));
            }
        }
        if( i < mx ){
            dp[i]=1;
        }
        else if(!ans.empty()){
            dp[i]= (*ans.begin())+1;
        }
        if(dp[i]<inf){
            for(auto v:primus){
                ans.ins(dp[i]);
                ev.ins({i + v,v});
            }
        }
    }
 
 
    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 2 ms 1104 KB Output is correct
2 Correct 17 ms 1240 KB Output is correct
3 Correct 7 ms 1104 KB Output is correct
4 Correct 5 ms 1104 KB Output is correct
5 Correct 5 ms 1104 KB Output is correct
6 Correct 3 ms 1104 KB Output is correct
7 Correct 7 ms 1104 KB Output is correct
8 Correct 16 ms 1104 KB Output is correct
9 Correct 24 ms 1008 KB Output is correct
10 Correct 28 ms 1024 KB Output is correct
11 Correct 17 ms 1120 KB Output is correct
12 Correct 3 ms 1104 KB Output is correct
13 Correct 51 ms 1196 KB Output is correct
14 Correct 50 ms 1352 KB Output is correct
15 Correct 16 ms 1104 KB Output is correct
16 Correct 17 ms 1272 KB Output is correct
17 Correct 12 ms 1104 KB Output is correct
18 Correct 4 ms 1104 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 3664 KB Execution killed with signal 11
2 Runtime error 38 ms 13788 KB Execution killed with signal 11
3 Runtime error 92 ms 11848 KB Execution killed with signal 11
4 Runtime error 13 ms 2640 KB Execution killed with signal 11
5 Runtime error 53 ms 9144 KB Execution killed with signal 11
6 Runtime error 16 ms 2384 KB Execution killed with signal 11
7 Runtime error 11 ms 3664 KB Execution killed with signal 11
8 Runtime error 14 ms 2384 KB Execution killed with signal 11
9 Runtime error 70 ms 11796 KB Execution killed with signal 11
10 Runtime error 95 ms 11860 KB Execution killed with signal 11
11 Runtime error 89 ms 8068 KB Execution killed with signal 11
12 Runtime error 27 ms 2488 KB Execution killed with signal 11
13 Runtime error 8 ms 2540 KB Execution killed with signal 11
14 Runtime error 14 ms 2640 KB Execution killed with signal 11
15 Runtime error 63 ms 7868 KB Execution killed with signal 11
16 Runtime error 41 ms 13884 KB Execution killed with signal 11
17 Runtime error 52 ms 2736 KB Execution killed with signal 11
18 Runtime error 82 ms 15432 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 9032 KB Execution killed with signal 11
2 Runtime error 85 ms 9564 KB Execution killed with signal 11
3 Runtime error 88 ms 9288 KB Execution killed with signal 11
4 Runtime error 32 ms 2928 KB Execution killed with signal 11
5 Runtime error 38 ms 14956 KB Execution killed with signal 11
6 Runtime error 49 ms 3656 KB Execution killed with signal 11
7 Runtime error 62 ms 15308 KB Execution killed with signal 11
8 Runtime error 79 ms 8976 KB Execution killed with signal 11
9 Runtime error 70 ms 9032 KB Execution killed with signal 11
10 Runtime error 32 ms 3352 KB Execution killed with signal 11
11 Runtime error 23 ms 3164 KB Execution killed with signal 11
12 Runtime error 48 ms 3508 KB Execution killed with signal 11
13 Runtime error 71 ms 6764 KB Execution killed with signal 11
14 Runtime error 30 ms 2088 KB Execution killed with signal 11
15 Runtime error 65 ms 3412 KB Execution killed with signal 11
16 Runtime error 65 ms 3668 KB Execution killed with signal 11
17 Runtime error 51 ms 8528 KB Execution killed with signal 11
18 Runtime error 84 ms 9556 KB Execution killed with signal 11
19 Runtime error 13 ms 2908 KB Execution killed with signal 11
20 Runtime error 85 ms 9240 KB Execution killed with signal 11
21 Runtime error 37 ms 2136 KB Execution killed with signal 11
22 Runtime error 94 ms 15544 KB Execution killed with signal 11
23 Runtime error 17 ms 6236 KB Execution killed with signal 11
24 Runtime error 7 ms 2400 KB Execution killed with signal 11
25 Runtime error 32 ms 2644 KB Execution killed with signal 11
26 Runtime error 34 ms 2900 KB Execution killed with signal 11
27 Runtime error 117 ms 15624 KB Execution killed with signal 11
28 Runtime error 11 ms 2384 KB Execution killed with signal 11
29 Runtime error 74 ms 15684 KB Execution killed with signal 11
30 Runtime error 54 ms 11848 KB Execution killed with signal 11
31 Runtime error 13 ms 2896 KB Execution killed with signal 11
32 Runtime error 17 ms 2640 KB Execution killed with signal 11
33 Runtime error 5 ms 2384 KB Execution killed with signal 11
34 Runtime error 57 ms 15368 KB Execution killed with signal 11
35 Runtime error 12 ms 2580 KB Execution killed with signal 11
36 Runtime error 92 ms 14344 KB Execution killed with signal 11
37 Runtime error 41 ms 14920 KB Execution killed with signal 11
38 Runtime error 51 ms 3672 KB Execution killed with signal 11
39 Runtime error 9 ms 2456 KB Execution killed with signal 11
40 Runtime error 45 ms 3700 KB Execution killed with signal 11
41 Runtime error 65 ms 15204 KB Execution killed with signal 11
42 Runtime error 69 ms 2644 KB Execution killed with signal 11