oj.uz

Submission #1109617

# Submission time Handle Problem Language Result Execution time Memory
1109617 2024-11-07T07:28:13 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
22.0635 / 100
 1000 ms 85552 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];
void fast(){
    int n,q;
    cin>>n>>q;
    multiset<int> ans; 
    int mx = 0;
    priority_queue<pair<int,int>> ev;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        // event[p].pb(p);
        ev.push({-p,p});
        mx=max(mx,p);
    }
    vector<int> primus;
    for(int i =1;i<sze;i++){
        dp[i]=inf;
        primus.clear();
        while(!ev.empty() && (-(ev.top().first )) ==i ) {
            auto beg = ev.top();
            ev.pop();
            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.push({-(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
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 78672 KB Output is correct
2 Execution timed out 1091 ms 74372 KB Time limit exceeded
3 Correct 44 ms 78664 KB Output is correct
4 Correct 144 ms 78664 KB Output is correct
5 Correct 288 ms 78664 KB Output is correct
6 Correct 33 ms 78672 KB Output is correct
7 Correct 42 ms 78580 KB Output is correct
8 Correct 87 ms 78664 KB Output is correct
9 Execution timed out 1085 ms 75640 KB Time limit exceeded
10 Execution timed out 1049 ms 53832 KB Time limit exceeded
11 Execution timed out 1066 ms 73644 KB Time limit exceeded
12 Correct 122 ms 78920 KB Output is correct
13 Execution timed out 1066 ms 21180 KB Time limit exceeded
14 Execution timed out 1067 ms 21064 KB Time limit exceeded
15 Execution timed out 1078 ms 78664 KB Time limit exceeded
16 Execution timed out 1055 ms 74372 KB Time limit exceeded
17 Correct 425 ms 78520 KB Output is correct
18 Correct 154 ms 78508 KB Output is correct

Subtask #2
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 79288 KB Output is correct
2 Correct 589 ms 83084 KB Output is correct
3 Execution timed out 1050 ms 20124 KB Time limit exceeded
4 Execution timed out 1036 ms 78692 KB Time limit exceeded
5 Execution timed out 1064 ms 26408 KB Time limit exceeded
6 Execution timed out 1068 ms 78664 KB Time limit exceeded
7 Correct 450 ms 79300 KB Output is correct
8 Correct 844 ms 78664 KB Output is correct
9 Execution timed out 1069 ms 26544 KB Time limit exceeded
10 Execution timed out 1046 ms 20116 KB Time limit exceeded
11 Execution timed out 1065 ms 17284 KB Time limit exceeded
12 Execution timed out 1059 ms 41736 KB Time limit exceeded
13 Correct 471 ms 78908 KB Output is correct
14 Execution timed out 1008 ms 78920 KB Time limit exceeded
15 Execution timed out 1054 ms 19652 KB Time limit exceeded
16 Correct 639 ms 83136 KB Output is correct
17 Execution timed out 1061 ms 21320 KB Time limit exceeded
18 Execution timed out 1071 ms 27884 KB Time limit exceeded

Subtask #3
4.28571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 20164 KB Time limit exceeded
2 Execution timed out 1073 ms 16068 KB Time limit exceeded
3 Execution timed out 1046 ms 18128 KB Time limit exceeded
4 Execution timed out 1074 ms 37748 KB Time limit exceeded
5 Incorrect 884 ms 85552 KB Output isn't correct
6 Execution timed out 1068 ms 23672 KB Time limit exceeded
7 Execution timed out 1049 ms 40204 KB Time limit exceeded
8 Execution timed out 1071 ms 20180 KB Time limit exceeded
9 Execution timed out 1064 ms 20168 KB Time limit exceeded
10 Execution timed out 1070 ms 35656 KB Time limit exceeded
11 Execution timed out 1046 ms 45968 KB Time limit exceeded
12 Execution timed out 1065 ms 25588 KB Time limit exceeded
13 Execution timed out 1066 ms 18920 KB Time limit exceeded
14 Execution timed out 1063 ms 43660 KB Time limit exceeded
15 Execution timed out 1066 ms 19272 KB Time limit exceeded
16 Execution timed out 1068 ms 19520 KB Time limit exceeded
17 Execution timed out 1076 ms 23948 KB Time limit exceeded
18 Execution timed out 1066 ms 18276 KB Time limit exceeded
19 Incorrect 818 ms 78860 KB Output isn't correct
20 Execution timed out 1054 ms 15896 KB Time limit exceeded
21 Execution timed out 1063 ms 31400 KB Time limit exceeded
22 Execution timed out 1069 ms 21608 KB Time limit exceeded
23 Correct 896 ms 80720 KB Output is correct
24 Correct 398 ms 78920 KB Output is correct
25 Execution timed out 1071 ms 35656 KB Time limit exceeded
26 Execution timed out 1073 ms 35656 KB Time limit exceeded
27 Execution timed out 1071 ms 21696 KB Time limit exceeded
28 Incorrect 658 ms 78864 KB Output isn't correct
29 Execution timed out 1056 ms 27888 KB Time limit exceeded
30 Execution timed out 1072 ms 30400 KB Time limit exceeded
31 Correct 890 ms 79180 KB Output is correct
32 Execution timed out 1047 ms 72504 KB Time limit exceeded
33 Incorrect 241 ms 78920 KB Output isn't correct
34 Execution timed out 1074 ms 40208 KB Time limit exceeded
35 Incorrect 780 ms 78920 KB Output isn't correct
36 Execution timed out 1070 ms 21128 KB Time limit exceeded
37 Incorrect 803 ms 85480 KB Output isn't correct
38 Execution timed out 1073 ms 23680 KB Time limit exceeded
39 Incorrect 551 ms 78920 KB Output isn't correct
40 Execution timed out 1059 ms 25804 KB Time limit exceeded
41 Execution timed out 1074 ms 38080 KB Time limit exceeded
42 Execution timed out 1061 ms 19260 KB Time limit exceeded