oj.uz

Submission #1109613

# Submission time Handle Problem Language Result Execution time Memory
1109613 2024-11-07T07:12:41 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
25.2381 / 100
 1000 ms 89124 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;
    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
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 78672 KB Output is correct
2 Execution timed out 1055 ms 57992 KB Time limit exceeded
3 Correct 44 ms 78664 KB Output is correct
4 Correct 191 ms 78740 KB Output is correct
5 Correct 392 ms 78512 KB Output is correct
6 Correct 30 ms 78672 KB Output is correct
7 Correct 41 ms 78664 KB Output is correct
8 Correct 110 ms 78672 KB Output is correct
9 Execution timed out 1067 ms 51872 KB Time limit exceeded
10 Execution timed out 1065 ms 41648 KB Time limit exceeded
11 Execution timed out 1081 ms 56024 KB Time limit exceeded
12 Correct 144 ms 78664 KB Output is correct
13 Execution timed out 1063 ms 19176 KB Time limit exceeded
14 Execution timed out 1065 ms 19184 KB Time limit exceeded
15 Execution timed out 1053 ms 60128 KB Time limit exceeded
16 Execution timed out 1050 ms 55940 KB Time limit exceeded
17 Correct 579 ms 78664 KB Output is correct
18 Correct 194 ms 78732 KB Output is correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 79820 KB Output is correct
2 Execution timed out 1020 ms 89124 KB Time limit exceeded
3 Execution timed out 1057 ms 18656 KB Time limit exceeded
4 Execution timed out 1079 ms 68676 KB Time limit exceeded
5 Execution timed out 1070 ms 22456 KB Time limit exceeded
6 Execution timed out 1047 ms 64284 KB Time limit exceeded
7 Correct 669 ms 79944 KB Output is correct
8 Correct 980 ms 78664 KB Output is correct
9 Execution timed out 1056 ms 23400 KB Time limit exceeded
10 Execution timed out 1054 ms 18788 KB Time limit exceeded
11 Execution timed out 1030 ms 15076 KB Time limit exceeded
12 Execution timed out 1064 ms 33608 KB Time limit exceeded
13 Correct 571 ms 78920 KB Output is correct
14 Execution timed out 1071 ms 66376 KB Time limit exceeded
15 Execution timed out 1075 ms 17464 KB Time limit exceeded
16 Correct 898 ms 88848 KB Output is correct
17 Execution timed out 1061 ms 17360 KB Time limit exceeded
18 Execution timed out 1064 ms 25416 KB Time limit exceeded

Subtask #3
8.57142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 18680 KB Time limit exceeded
2 Execution timed out 1059 ms 16712 KB Time limit exceeded
3 Execution timed out 1063 ms 16168 KB Time limit exceeded
4 Execution timed out 1071 ms 29684 KB Time limit exceeded
5 Execution timed out 1069 ms 79132 KB Time limit exceeded
6 Execution timed out 1055 ms 17736 KB Time limit exceeded
7 Execution timed out 1057 ms 34376 KB Time limit exceeded
8 Execution timed out 1050 ms 18536 KB Time limit exceeded
9 Execution timed out 1066 ms 20248 KB Time limit exceeded
10 Execution timed out 1058 ms 27924 KB Time limit exceeded
11 Execution timed out 1058 ms 40016 KB Time limit exceeded
12 Execution timed out 1062 ms 19528 KB Time limit exceeded
13 Execution timed out 1067 ms 16212 KB Time limit exceeded
14 Execution timed out 1067 ms 33428 KB Time limit exceeded
15 Execution timed out 1045 ms 17620 KB Time limit exceeded
16 Execution timed out 1062 ms 15756 KB Time limit exceeded
17 Execution timed out 1060 ms 22088 KB Time limit exceeded
18 Execution timed out 1069 ms 16864 KB Time limit exceeded
19 Correct 959 ms 79320 KB Output is correct
20 Execution timed out 1029 ms 16196 KB Time limit exceeded
21 Execution timed out 1069 ms 27276 KB Time limit exceeded
22 Execution timed out 1049 ms 21072 KB Time limit exceeded
23 Execution timed out 1068 ms 75592 KB Time limit exceeded
24 Correct 463 ms 79708 KB Output is correct
25 Execution timed out 1057 ms 29624 KB Time limit exceeded
26 Execution timed out 1049 ms 27636 KB Time limit exceeded
27 Execution timed out 1065 ms 20876 KB Time limit exceeded
28 Correct 776 ms 79688 KB Output is correct
29 Execution timed out 1053 ms 25824 KB Time limit exceeded
30 Execution timed out 1057 ms 25068 KB Time limit exceeded
31 Execution timed out 1071 ms 76988 KB Time limit exceeded
32 Execution timed out 1068 ms 58296 KB Time limit exceeded
33 Correct 286 ms 79688 KB Output is correct
34 Execution timed out 1055 ms 32416 KB Time limit exceeded
35 Correct 919 ms 79960 KB Output is correct
36 Execution timed out 1053 ms 20040 KB Time limit exceeded
37 Execution timed out 1051 ms 79708 KB Time limit exceeded
38 Execution timed out 1053 ms 17912 KB Time limit exceeded
39 Correct 719 ms 79824 KB Output is correct
40 Execution timed out 1051 ms 22160 KB Time limit exceeded
41 Execution timed out 1055 ms 31376 KB Time limit exceeded
42 Execution timed out 1064 ms 17224 KB Time limit exceeded