oj.uz

Submission #1109616

# Submission time Handle Problem Language Result Execution time Memory
1109616 2024-11-07T07:20:52 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 939 ms 33096 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 = 1e6 +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){
                if(i + v <sze){
                    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 6 ms 8272 KB Output is correct
2 Correct 143 ms 8060 KB Output is correct
3 Correct 17 ms 8272 KB Output is correct
4 Correct 20 ms 8272 KB Output is correct
5 Correct 39 ms 8256 KB Output is correct
6 Correct 8 ms 8272 KB Output is correct
7 Correct 21 ms 8272 KB Output is correct
8 Correct 83 ms 8264 KB Output is correct
9 Correct 153 ms 8044 KB Output is correct
10 Correct 212 ms 8264 KB Output is correct
11 Correct 159 ms 8264 KB Output is correct
12 Correct 17 ms 8088 KB Output is correct
13 Correct 479 ms 8608 KB Output is correct
14 Correct 514 ms 8264 KB Output is correct
15 Correct 142 ms 8264 KB Output is correct
16 Correct 141 ms 8280 KB Output is correct
17 Correct 74 ms 8268 KB Output is correct
18 Correct 23 ms 8228 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 18416 KB Execution killed with signal 11
2 Runtime error 100 ms 28488 KB Execution killed with signal 11
3 Runtime error 794 ms 28768 KB Execution killed with signal 11
4 Runtime error 127 ms 16968 KB Execution killed with signal 11
5 Runtime error 411 ms 24952 KB Execution killed with signal 11
6 Runtime error 132 ms 16624 KB Execution killed with signal 11
7 Runtime error 58 ms 18500 KB Execution killed with signal 11
8 Runtime error 116 ms 16612 KB Execution killed with signal 11
9 Runtime error 612 ms 28332 KB Execution killed with signal 11
10 Runtime error 939 ms 28780 KB Execution killed with signal 11
11 Runtime error 821 ms 25216 KB Execution killed with signal 11
12 Runtime error 275 ms 16712 KB Execution killed with signal 11
13 Runtime error 85 ms 17088 KB Execution killed with signal 11
14 Runtime error 142 ms 17104 KB Execution killed with signal 11
15 Runtime error 630 ms 24120 KB Execution killed with signal 11
16 Runtime error 109 ms 28488 KB Execution killed with signal 11
17 Runtime error 534 ms 17008 KB Execution killed with signal 11
18 Runtime error 609 ms 31804 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 685 ms 25232 KB Execution killed with signal 11
2 Runtime error 840 ms 26696 KB Execution killed with signal 11
3 Runtime error 895 ms 26404 KB Execution killed with signal 11
4 Runtime error 313 ms 17072 KB Execution killed with signal 11
5 Runtime error 109 ms 30024 KB Execution killed with signal 11
6 Runtime error 532 ms 18224 KB Execution killed with signal 11
7 Runtime error 329 ms 31304 KB Execution killed with signal 11
8 Runtime error 668 ms 25160 KB Execution killed with signal 11
9 Runtime error 630 ms 25188 KB Execution killed with signal 11
10 Runtime error 380 ms 17736 KB Execution killed with signal 11
11 Runtime error 257 ms 17224 KB Execution killed with signal 11
12 Runtime error 483 ms 17736 KB Execution killed with signal 11
13 Runtime error 711 ms 23112 KB Execution killed with signal 11
14 Runtime error 268 ms 16456 KB Execution killed with signal 11
15 Runtime error 583 ms 17480 KB Execution killed with signal 11
16 Runtime error 690 ms 17832 KB Execution killed with signal 11
17 Runtime error 535 ms 24876 KB Execution killed with signal 11
18 Runtime error 822 ms 26756 KB Execution killed with signal 11
19 Runtime error 99 ms 17480 KB Execution killed with signal 11
20 Runtime error 890 ms 26324 KB Execution killed with signal 11
21 Runtime error 346 ms 16268 KB Execution killed with signal 11
22 Runtime error 841 ms 32584 KB Execution killed with signal 11
23 Runtime error 102 ms 21616 KB Execution killed with signal 11
24 Runtime error 58 ms 16636 KB Execution killed with signal 11
25 Runtime error 330 ms 16968 KB Execution killed with signal 11
26 Runtime error 304 ms 17112 KB Execution killed with signal 11
27 Runtime error 868 ms 33096 KB Execution killed with signal 11
28 Runtime error 97 ms 16456 KB Execution killed with signal 11
29 Runtime error 525 ms 32584 KB Execution killed with signal 11
30 Runtime error 443 ms 28744 KB Execution killed with signal 11
31 Runtime error 138 ms 17416 KB Execution killed with signal 11
32 Runtime error 158 ms 17084 KB Execution killed with signal 11
33 Runtime error 38 ms 16712 KB Execution killed with signal 11
34 Runtime error 353 ms 31304 KB Execution killed with signal 11
35 Runtime error 110 ms 16988 KB Execution killed with signal 11
36 Runtime error 785 ms 30792 KB Execution killed with signal 11
37 Runtime error 107 ms 30024 KB Execution killed with signal 11
38 Runtime error 541 ms 18248 KB Execution killed with signal 11
39 Runtime error 80 ms 16968 KB Execution killed with signal 11
40 Runtime error 495 ms 18508 KB Execution killed with signal 11
41 Runtime error 425 ms 30792 KB Execution killed with signal 11
42 Runtime error 557 ms 17092 KB Execution killed with signal 11