oj.uz

Submission #1109623

# Submission time Handle Problem Language Result Execution time Memory
1109623 2024-11-07T07:36:46 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++17
48.8889 / 100
 1000 ms 81088 KB 
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("inline")
#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;
}

Compilation message

brunhilda.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization ("O3")
      | 
brunhilda.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      | 
brunhilda.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("inline")
      |

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78512 KB Output is correct
2 Correct 374 ms 78656 KB Output is correct
3 Correct 187 ms 78468 KB Output is correct
4 Correct 99 ms 78668 KB Output is correct
5 Correct 195 ms 78472 KB Output is correct
6 Correct 44 ms 78664 KB Output is correct
7 Correct 181 ms 78664 KB Output is correct
8 Correct 232 ms 78664 KB Output is correct
9 Correct 514 ms 78656 KB Output is correct
10 Correct 658 ms 78664 KB Output is correct
11 Correct 510 ms 78716 KB Output is correct
12 Correct 81 ms 78664 KB Output is correct
13 Execution timed out 1076 ms 56044 KB Time limit exceeded
14 Execution timed out 1060 ms 49864 KB Time limit exceeded
15 Correct 416 ms 78664 KB Output is correct
16 Correct 379 ms 78664 KB Output is correct
17 Correct 238 ms 78572 KB Output is correct
18 Correct 106 ms 78524 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 79056 KB Output is correct
2 Correct 343 ms 80908 KB Output is correct
3 Execution timed out 1053 ms 33552 KB Time limit exceeded
4 Correct 475 ms 78664 KB Output is correct
5 Execution timed out 1060 ms 58820 KB Time limit exceeded
6 Correct 415 ms 78664 KB Output is correct
7 Correct 247 ms 79052 KB Output is correct
8 Correct 396 ms 78616 KB Output is correct
9 Execution timed out 1054 ms 46148 KB Time limit exceeded
10 Execution timed out 1072 ms 35632 KB Time limit exceeded
11 Execution timed out 1066 ms 36516 KB Time limit exceeded
12 Correct 851 ms 78812 KB Output is correct
13 Correct 226 ms 78664 KB Output is correct
14 Correct 483 ms 78676 KB Output is correct
15 Execution timed out 1064 ms 42444 KB Time limit exceeded
16 Correct 325 ms 80832 KB Output is correct
17 Execution timed out 1070 ms 52032 KB Time limit exceeded
18 Execution timed out 1050 ms 47808 KB Time limit exceeded

Subtask #3
20.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 46620 KB Time limit exceeded
2 Execution timed out 1052 ms 36292 KB Time limit exceeded
3 Execution timed out 1063 ms 34244 KB Time limit exceeded
4 Execution timed out 1055 ms 79076 KB Time limit exceeded
5 Correct 472 ms 81088 KB Output is correct
6 Execution timed out 1066 ms 54228 KB Time limit exceeded
7 Execution timed out 1064 ms 64312 KB Time limit exceeded
8 Execution timed out 1054 ms 40484 KB Time limit exceeded
9 Execution timed out 1060 ms 42580 KB Time limit exceeded
10 Execution timed out 1071 ms 78936 KB Time limit exceeded
11 Correct 801 ms 78968 KB Output is correct
12 Execution timed out 1063 ms 58536 KB Time limit exceeded
13 Execution timed out 1062 ms 40136 KB Time limit exceeded
14 Correct 787 ms 79084 KB Output is correct
15 Execution timed out 1067 ms 52140 KB Time limit exceeded
16 Execution timed out 1069 ms 45984 KB Time limit exceeded
17 Execution timed out 1052 ms 52728 KB Time limit exceeded
18 Execution timed out 1051 ms 34244 KB Time limit exceeded
19 Correct 350 ms 78760 KB Output is correct
20 Execution timed out 1071 ms 36292 KB Time limit exceeded
21 Execution timed out 1038 ms 79172 KB Time limit exceeded
22 Execution timed out 1043 ms 35608 KB Time limit exceeded
23 Correct 406 ms 79360 KB Output is correct
24 Correct 213 ms 78920 KB Output is correct
25 Execution timed out 1052 ms 79160 KB Time limit exceeded
26 Correct 934 ms 78944 KB Output is correct
27 Execution timed out 1048 ms 33592 KB Time limit exceeded
28 Correct 285 ms 78996 KB Output is correct
29 Execution timed out 1082 ms 47916 KB Time limit exceeded
30 Execution timed out 1040 ms 50008 KB Time limit exceeded
31 Correct 420 ms 79508 KB Output is correct
32 Correct 575 ms 79176 KB Output is correct
33 Correct 157 ms 78920 KB Output is correct
34 Execution timed out 1060 ms 66420 KB Time limit exceeded
35 Correct 375 ms 79044 KB Output is correct
36 Execution timed out 1082 ms 37652 KB Time limit exceeded
37 Correct 433 ms 81088 KB Output is correct
38 Execution timed out 1062 ms 52152 KB Time limit exceeded
39 Correct 299 ms 78944 KB Output is correct
40 Execution timed out 1053 ms 64688 KB Time limit exceeded
41 Execution timed out 1066 ms 70420 KB Time limit exceeded
42 Execution timed out 1062 ms 47888 KB Time limit exceeded