oj.uz

Submission #1109622

# Submission time Handle Problem Language Result Execution time Memory
1109622 2024-11-07T07:35:05 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++11
50.3175 / 100
 1000 ms 81088 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;
        map<int,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;
        int c,prev;
        for(int i =1;i<sze;i++){
            dp[i]=inf;
            primus.clear();
            c=0;
            while(!ev.empty() && (-(ev.top().first )) ==i ) {
                auto beg = ev.top();
                ev.pop();
                c++;
                // cout<<i<<" "<<beg.first<<" "<<beg.second<<endl;
                if( (i + beg.second) < sze){
                    ev.push({ -(i + beg.second) , beg.second });
                }
                prev=  dp[i - beg.second];
                if(i != beg.second){
                    if(ans.find(prev)!=ans.end()){
                        if( (--ans[prev]) ==0){
                            ans.erase(prev);
                        }
                    }
                }
            }
            if( i < mx ){
                dp[i]=1;
            }
            else if(!ans.empty()){
                dp[i]= (*ans.begin()).first+1;
            }
            if(dp[i]<inf){
                ans[dp[i]]+=c;
            }
        }
     
     
        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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 78664 KB Output is correct
2 Correct 386 ms 78672 KB Output is correct
3 Correct 189 ms 78664 KB Output is correct
4 Correct 116 ms 78744 KB Output is correct
5 Correct 185 ms 78664 KB Output is correct
6 Correct 48 ms 78664 KB Output is correct
7 Correct 187 ms 78664 KB Output is correct
8 Correct 246 ms 78732 KB Output is correct
9 Correct 502 ms 78688 KB Output is correct
10 Correct 662 ms 78720 KB Output is correct
11 Correct 528 ms 78664 KB Output is correct
12 Correct 90 ms 78664 KB Output is correct
13 Execution timed out 1063 ms 51912 KB Time limit exceeded
14 Execution timed out 1058 ms 53832 KB Time limit exceeded
15 Correct 425 ms 78516 KB Output is correct
16 Correct 370 ms 78728 KB Output is correct
17 Correct 239 ms 78672 KB Output is correct
18 Correct 101 ms 78664 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 79056 KB Output is correct
2 Correct 359 ms 80664 KB Output is correct
3 Execution timed out 1056 ms 33472 KB Time limit exceeded
4 Correct 474 ms 78680 KB Output is correct
5 Execution timed out 1070 ms 58816 KB Time limit exceeded
6 Correct 411 ms 78664 KB Output is correct
7 Correct 250 ms 78864 KB Output is correct
8 Correct 417 ms 78752 KB Output is correct
9 Execution timed out 1075 ms 47808 KB Time limit exceeded
10 Execution timed out 1043 ms 33468 KB Time limit exceeded
11 Execution timed out 1064 ms 36224 KB Time limit exceeded
12 Correct 858 ms 78664 KB Output is correct
13 Correct 252 ms 78664 KB Output is correct
14 Correct 485 ms 78692 KB Output is correct
15 Execution timed out 1055 ms 42444 KB Time limit exceeded
16 Correct 334 ms 80832 KB Output is correct
17 Execution timed out 1068 ms 50200 KB Time limit exceeded
18 Execution timed out 1060 ms 49956 KB Time limit exceeded

Subtask #3
21.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 42576 KB Time limit exceeded
2 Execution timed out 1053 ms 32352 KB Time limit exceeded
3 Execution timed out 1075 ms 32300 KB Time limit exceeded
4 Correct 987 ms 78960 KB Output is correct
5 Correct 415 ms 80920 KB Output is correct
6 Execution timed out 1074 ms 56268 KB Time limit exceeded
7 Execution timed out 1054 ms 68460 KB Time limit exceeded
8 Execution timed out 1060 ms 44560 KB Time limit exceeded
9 Execution timed out 1074 ms 44576 KB Time limit exceeded
10 Execution timed out 1047 ms 78936 KB Time limit exceeded
11 Correct 757 ms 78916 KB Output is correct
12 Execution timed out 1059 ms 58264 KB Time limit exceeded
13 Execution timed out 1075 ms 40164 KB Time limit exceeded
14 Correct 786 ms 79108 KB Output is correct
15 Execution timed out 1070 ms 49992 KB Time limit exceeded
16 Execution timed out 1040 ms 41800 KB Time limit exceeded
17 Execution timed out 1061 ms 50680 KB Time limit exceeded
18 Execution timed out 1060 ms 34360 KB Time limit exceeded
19 Correct 366 ms 78764 KB Output is correct
20 Execution timed out 1067 ms 34332 KB Time limit exceeded
21 Execution timed out 1065 ms 78664 KB Time limit exceeded
22 Execution timed out 1052 ms 37568 KB Time limit exceeded
23 Correct 384 ms 79560 KB Output is correct
24 Correct 234 ms 79040 KB Output is correct
25 Execution timed out 1049 ms 78420 KB Time limit exceeded
26 Correct 999 ms 78920 KB Output is correct
27 Execution timed out 1070 ms 31492 KB Time limit exceeded
28 Correct 299 ms 78920 KB Output is correct
29 Execution timed out 1072 ms 47892 KB Time limit exceeded
30 Execution timed out 1068 ms 56148 KB Time limit exceeded
31 Correct 398 ms 78924 KB Output is correct
32 Correct 563 ms 78920 KB Output is correct
33 Correct 152 ms 78804 KB Output is correct
34 Execution timed out 1074 ms 68340 KB Time limit exceeded
35 Correct 364 ms 78920 KB Output is correct
36 Execution timed out 1076 ms 39712 KB Time limit exceeded
37 Correct 413 ms 81088 KB Output is correct
38 Execution timed out 1060 ms 56280 KB Time limit exceeded
39 Correct 319 ms 79084 KB Output is correct
40 Execution timed out 1076 ms 62408 KB Time limit exceeded
41 Execution timed out 1049 ms 66320 KB Time limit exceeded
42 Execution timed out 1063 ms 45640 KB Time limit exceeded