oj.uz

Submission #1109621

# Submission time Handle Problem Language Result Execution time Memory
1109621 2024-11-07T07:33:04 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
50.3175 / 100
 1000 ms 81188 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;
                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 52 ms 78664 KB Output is correct
2 Correct 399 ms 78716 KB Output is correct
3 Correct 170 ms 78720 KB Output is correct
4 Correct 101 ms 78664 KB Output is correct
5 Correct 176 ms 78476 KB Output is correct
6 Correct 54 ms 78552 KB Output is correct
7 Correct 188 ms 78712 KB Output is correct
8 Correct 241 ms 78476 KB Output is correct
9 Correct 502 ms 78644 KB Output is correct
10 Correct 655 ms 78664 KB Output is correct
11 Correct 504 ms 78672 KB Output is correct
12 Correct 82 ms 78492 KB Output is correct
13 Execution timed out 1041 ms 53920 KB Time limit exceeded
14 Execution timed out 1078 ms 53980 KB Time limit exceeded
15 Correct 414 ms 78708 KB Output is correct
16 Correct 368 ms 78512 KB Output is correct
17 Correct 225 ms 78740 KB Output is correct
18 Correct 110 ms 78664 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 79052 KB Output is correct
2 Correct 316 ms 80832 KB Output is correct
3 Execution timed out 1071 ms 37640 KB Time limit exceeded
4 Correct 469 ms 78592 KB Output is correct
5 Execution timed out 1077 ms 60964 KB Time limit exceeded
6 Correct 416 ms 78620 KB Output is correct
7 Correct 238 ms 78800 KB Output is correct
8 Correct 388 ms 78612 KB Output is correct
9 Execution timed out 1055 ms 49992 KB Time limit exceeded
10 Execution timed out 1065 ms 35520 KB Time limit exceeded
11 Execution timed out 1064 ms 38264 KB Time limit exceeded
12 Correct 833 ms 78588 KB Output is correct
13 Correct 215 ms 78668 KB Output is correct
14 Correct 479 ms 78724 KB Output is correct
15 Execution timed out 1054 ms 42436 KB Time limit exceeded
16 Correct 314 ms 80828 KB Output is correct
17 Execution timed out 1066 ms 52004 KB Time limit exceeded
18 Execution timed out 1055 ms 47808 KB Time limit exceeded

Subtask #3
21.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 44564 KB Time limit exceeded
2 Execution timed out 1055 ms 34388 KB Time limit exceeded
3 Execution timed out 1071 ms 34244 KB Time limit exceeded
4 Correct 944 ms 78920 KB Output is correct
5 Correct 391 ms 81188 KB Output is correct
6 Execution timed out 1048 ms 56512 KB Time limit exceeded
7 Execution timed out 1057 ms 70336 KB Time limit exceeded
8 Execution timed out 1065 ms 46528 KB Time limit exceeded
9 Execution timed out 1053 ms 44484 KB Time limit exceeded
10 Execution timed out 1030 ms 78976 KB Time limit exceeded
11 Correct 771 ms 78744 KB Output is correct
12 Execution timed out 1066 ms 56232 KB Time limit exceeded
13 Execution timed out 1054 ms 38088 KB Time limit exceeded
14 Correct 788 ms 79092 KB Output is correct
15 Execution timed out 1052 ms 50032 KB Time limit exceeded
16 Execution timed out 1036 ms 45948 KB Time limit exceeded
17 Execution timed out 1052 ms 56824 KB Time limit exceeded
18 Execution timed out 1075 ms 34360 KB Time limit exceeded
19 Correct 358 ms 78936 KB Output is correct
20 Execution timed out 1074 ms 34348 KB Time limit exceeded
21 Execution timed out 1074 ms 78408 KB Time limit exceeded
22 Execution timed out 1057 ms 37568 KB Time limit exceeded
23 Correct 401 ms 79560 KB Output is correct
24 Correct 230 ms 78920 KB Output is correct
25 Execution timed out 1062 ms 78940 KB Time limit exceeded
26 Correct 991 ms 78936 KB Output is correct
27 Execution timed out 1046 ms 31532 KB Time limit exceeded
28 Correct 293 ms 79012 KB Output is correct
29 Execution timed out 1075 ms 51916 KB Time limit exceeded
30 Execution timed out 1070 ms 58116 KB Time limit exceeded
31 Correct 397 ms 79008 KB Output is correct
32 Correct 528 ms 79084 KB Output is correct
33 Correct 143 ms 78920 KB Output is correct
34 Execution timed out 1086 ms 70336 KB Time limit exceeded
35 Correct 379 ms 79036 KB Output is correct
36 Execution timed out 1067 ms 35592 KB Time limit exceeded
37 Correct 409 ms 81088 KB Output is correct
38 Execution timed out 1069 ms 54088 KB Time limit exceeded
39 Correct 311 ms 78920 KB Output is correct
40 Execution timed out 1086 ms 68504 KB Time limit exceeded
41 Execution timed out 1067 ms 70484 KB Time limit exceeded
42 Execution timed out 1045 ms 45640 KB Time limit exceeded