Submission #1109622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109622		0pt1mus23	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	50.32 / 100	1076 ms	81088 KiB

brunhilda

    #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.77777777777778 / 20
• Subtask 2: 11.11111111111111 / 20
• Subtask 3: 21.428571428571427 / 60