oj.uz

답안 #1109626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109626 2024-11-07T07:42:20 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
2.22222 / 100
 1000 ms 262144 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;
    unordered_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);
    }
    int c,prev;
    pair<int,int> beg;
    for(int i =1;i<sze;i++){
        dp[i]=inf;
        c=0;
        while(!ev.empty() && (-(ev.top().first )) ==i ) {
            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[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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 311 ms 262144 KB Execution killed with signal 9
2 Runtime error 465 ms 262144 KB Execution killed with signal 9
3 Runtime error 394 ms 262144 KB Execution killed with signal 9
4 Runtime error 338 ms 262144 KB Execution killed with signal 9
5 Runtime error 380 ms 262144 KB Execution killed with signal 9
6 Runtime error 339 ms 262144 KB Execution killed with signal 9
7 Runtime error 413 ms 262144 KB Execution killed with signal 9
8 Runtime error 440 ms 262144 KB Execution killed with signal 9
9 Runtime error 551 ms 262144 KB Execution killed with signal 9
10 Runtime error 639 ms 262144 KB Execution killed with signal 9
11 Runtime error 567 ms 262144 KB Execution killed with signal 9
12 Runtime error 309 ms 262144 KB Execution killed with signal 9
13 Execution timed out 1073 ms 231016 KB Time limit exceeded
14 Execution timed out 1072 ms 224112 KB Time limit exceeded
15 Runtime error 538 ms 262144 KB Execution killed with signal 9
16 Runtime error 474 ms 262144 KB Execution killed with signal 9
17 Runtime error 392 ms 262144 KB Execution killed with signal 9
18 Runtime error 337 ms 262144 KB Execution killed with signal 9

Subtask #2
2.22222222222 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 450 ms 262144 KB Execution killed with signal 9
2 Correct 396 ms 123356 KB Output is correct
3 Execution timed out 1074 ms 79936 KB Time limit exceeded
4 Runtime error 599 ms 262144 KB Execution killed with signal 9
5 Execution timed out 1066 ms 209768 KB Time limit exceeded
6 Runtime error 534 ms 262144 KB Execution killed with signal 9
7 Runtime error 461 ms 262144 KB Execution killed with signal 9
8 Runtime error 504 ms 262144 KB Execution killed with signal 9
9 Execution timed out 1066 ms 148800 KB Time limit exceeded
10 Execution timed out 1074 ms 78548 KB Time limit exceeded
11 Execution timed out 1072 ms 135660 KB Time limit exceeded
12 Runtime error 818 ms 262144 KB Execution killed with signal 9
13 Runtime error 384 ms 262144 KB Execution killed with signal 9
14 Runtime error 510 ms 262144 KB Execution killed with signal 9
15 Execution timed out 1064 ms 194480 KB Time limit exceeded
16 Correct 384 ms 123208 KB Output is correct
17 Execution timed out 1082 ms 224800 KB Time limit exceeded
18 Execution timed out 1046 ms 68108 KB Time limit exceeded

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 181380 KB Time limit exceeded
2 Execution timed out 1074 ms 129188 KB Time limit exceeded
3 Execution timed out 1047 ms 117888 KB Time limit exceeded
4 Runtime error 875 ms 262144 KB Execution killed with signal 9
5 Runtime error 700 ms 262144 KB Execution killed with signal 9
6 Execution timed out 1069 ms 236164 KB Time limit exceeded
7 Execution timed out 1088 ms 210840 KB Time limit exceeded
8 Execution timed out 1064 ms 191360 KB Time limit exceeded
9 Execution timed out 1072 ms 193896 KB Time limit exceeded
10 Runtime error 954 ms 262144 KB Execution killed with signal 9
11 Runtime error 777 ms 262144 KB Execution killed with signal 9
12 Execution timed out 1086 ms 236484 KB Time limit exceeded
13 Execution timed out 1065 ms 146648 KB Time limit exceeded
14 Runtime error 684 ms 262144 KB Execution killed with signal 9
15 Execution timed out 1075 ms 224056 KB Time limit exceeded
16 Execution timed out 1079 ms 197700 KB Time limit exceeded
17 Execution timed out 1052 ms 207740 KB Time limit exceeded
18 Execution timed out 1075 ms 138916 KB Time limit exceeded
19 Runtime error 463 ms 262144 KB Execution killed with signal 9
20 Execution timed out 1073 ms 122948 KB Time limit exceeded
21 Runtime error 869 ms 262144 KB Execution killed with signal 9
22 Execution timed out 1075 ms 118672 KB Time limit exceeded
23 Runtime error 657 ms 262144 KB Execution killed with signal 9
24 Runtime error 393 ms 262144 KB Execution killed with signal 9
25 Runtime error 914 ms 262144 KB Execution killed with signal 9
26 Runtime error 892 ms 262144 KB Execution killed with signal 9
27 Execution timed out 1067 ms 80200 KB Time limit exceeded
28 Runtime error 462 ms 262144 KB Execution killed with signal 9
29 Execution timed out 1073 ms 146116 KB Time limit exceeded
30 Execution timed out 1083 ms 197908 KB Time limit exceeded
31 Runtime error 495 ms 262144 KB Execution killed with signal 9
32 Runtime error 590 ms 262144 KB Execution killed with signal 9
33 Runtime error 368 ms 262144 KB Execution killed with signal 9
34 Execution timed out 1081 ms 151764 KB Time limit exceeded
35 Runtime error 486 ms 262144 KB Execution killed with signal 9
36 Execution timed out 1063 ms 118296 KB Time limit exceeded
37 Runtime error 808 ms 262144 KB Execution killed with signal 9
38 Execution timed out 1068 ms 227768 KB Time limit exceeded
39 Runtime error 455 ms 262144 KB Execution killed with signal 9
40 Execution timed out 1097 ms 256512 KB Time limit exceeded
41 Execution timed out 1058 ms 85500 KB Time limit exceeded
42 Execution timed out 1073 ms 213828 KB Time limit exceeded