oj.uz

답안 #1109637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109637 2024-11-07T08:17:44 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
42.381 / 100
 1000 ms 85064 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;
    int mx = 0;

    set<pair<int,int>> var;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        mx=max(mx,p);
        var.ins({p,p});
    }
    for(int i=1;i<sze;i++){
        dp[i]=inf;
        while(!var.empty()){
            auto it = *var.begin();
            if( it.first + it.second<=i){
                // cout<<i<<" "<<it.first<<" "<<it.second<<endl;
                if(it.first + it.second < sze){
                    var.ins({it.first + it.second,it.second});
                }
                var.erase(var.begin());
            }
            else{
                break;
            }
        }
        if(i<mx){
            dp[i]=1;
        }
        else{
            // cout<<i<<" "<<var.size()<<endl;
            if(!var.empty()){

                auto it = *var.begin();
                // cout<<i<<" "<<it.first<<endl;
                dp[i]= dp[it.first] +1;
            }
        }
    }

 
    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
16.6666666667 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 78496 KB Output is correct
2 Correct 569 ms 78664 KB Output is correct
3 Correct 357 ms 78664 KB Output is correct
4 Correct 87 ms 78500 KB Output is correct
5 Correct 187 ms 78668 KB Output is correct
6 Correct 92 ms 78748 KB Output is correct
7 Correct 309 ms 78716 KB Output is correct
8 Correct 501 ms 78664 KB Output is correct
9 Correct 769 ms 78664 KB Output is correct
10 Execution timed out 1053 ms 76664 KB Time limit exceeded
11 Correct 784 ms 78596 KB Output is correct
12 Correct 71 ms 78664 KB Output is correct
13 Execution timed out 1084 ms 33464 KB Time limit exceeded
14 Execution timed out 1072 ms 35516 KB Time limit exceeded
15 Correct 664 ms 78720 KB Output is correct
16 Correct 575 ms 78664 KB Output is correct
17 Correct 303 ms 78604 KB Output is correct
18 Correct 113 ms 78512 KB Output is correct

Subtask #2
10.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 79352 KB Output is correct
2 Correct 289 ms 84228 KB Output is correct
3 Execution timed out 1063 ms 29512 KB Time limit exceeded
4 Correct 625 ms 78916 KB Output is correct
5 Execution timed out 1054 ms 48928 KB Time limit exceeded
6 Correct 506 ms 78664 KB Output is correct
7 Correct 329 ms 79224 KB Output is correct
8 Correct 489 ms 78664 KB Output is correct
9 Execution timed out 1052 ms 41968 KB Time limit exceeded
10 Execution timed out 1066 ms 29512 KB Time limit exceeded
11 Execution timed out 1057 ms 27716 KB Time limit exceeded
12 Execution timed out 1062 ms 70456 KB Time limit exceeded
13 Correct 231 ms 78660 KB Output is correct
14 Correct 605 ms 78772 KB Output is correct
15 Execution timed out 1040 ms 33796 KB Time limit exceeded
16 Correct 282 ms 84296 KB Output is correct
17 Execution timed out 1077 ms 33612 KB Time limit exceeded
18 Execution timed out 1051 ms 44076 KB Time limit exceeded

Subtask #3
15.7142857143 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 36532 KB Time limit exceeded
2 Execution timed out 1055 ms 28484 KB Time limit exceeded
3 Execution timed out 1053 ms 28360 KB Time limit exceeded
4 Execution timed out 1066 ms 64328 KB Time limit exceeded
5 Correct 521 ms 85064 KB Output is correct
6 Execution timed out 1055 ms 38060 KB Time limit exceeded
7 Execution timed out 1069 ms 62272 KB Time limit exceeded
8 Execution timed out 1059 ms 34524 KB Time limit exceeded
9 Execution timed out 1048 ms 36424 KB Time limit exceeded
10 Execution timed out 1069 ms 60488 KB Time limit exceeded
11 Execution timed out 1027 ms 79028 KB Time limit exceeded
12 Execution timed out 1066 ms 39916 KB Time limit exceeded
13 Execution timed out 1061 ms 29152 KB Time limit exceeded
14 Execution timed out 1061 ms 66456 KB Time limit exceeded
15 Execution timed out 1065 ms 35656 KB Time limit exceeded
16 Execution timed out 1067 ms 29760 KB Time limit exceeded
17 Execution timed out 1041 ms 40336 KB Time limit exceeded
18 Execution timed out 1061 ms 28508 KB Time limit exceeded
19 Correct 334 ms 78928 KB Output is correct
20 Execution timed out 1064 ms 30396 KB Time limit exceeded
21 Execution timed out 1059 ms 49736 KB Time limit exceeded
22 Execution timed out 1070 ms 35600 KB Time limit exceeded
23 Correct 632 ms 80612 KB Output is correct
24 Correct 235 ms 78920 KB Output is correct
25 Execution timed out 1062 ms 58160 KB Time limit exceeded
26 Execution timed out 1053 ms 64328 KB Time limit exceeded
27 Execution timed out 1066 ms 33532 KB Time limit exceeded
28 Correct 340 ms 78920 KB Output is correct
29 Execution timed out 1074 ms 43800 KB Time limit exceeded
30 Execution timed out 1066 ms 43996 KB Time limit exceeded
31 Correct 530 ms 78996 KB Output is correct
32 Correct 690 ms 79176 KB Output is correct
33 Correct 132 ms 78840 KB Output is correct
34 Execution timed out 1063 ms 62256 KB Time limit exceeded
35 Correct 434 ms 78924 KB Output is correct
36 Execution timed out 1073 ms 34964 KB Time limit exceeded
37 Correct 493 ms 85020 KB Output is correct
38 Execution timed out 1060 ms 37960 KB Time limit exceeded
39 Correct 349 ms 78920 KB Output is correct
40 Execution timed out 1086 ms 46292 KB Time limit exceeded
41 Execution timed out 1062 ms 66392 KB Time limit exceeded
42 Execution timed out 1065 ms 33632 KB Time limit exceeded