#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
78664 KB |
Output is correct |
2 |
Correct |
386 ms |
78672 KB |
Output is correct |
3 |
Correct |
189 ms |
78664 KB |
Output is correct |
4 |
Correct |
116 ms |
78744 KB |
Output is correct |
5 |
Correct |
185 ms |
78664 KB |
Output is correct |
6 |
Correct |
48 ms |
78664 KB |
Output is correct |
7 |
Correct |
187 ms |
78664 KB |
Output is correct |
8 |
Correct |
246 ms |
78732 KB |
Output is correct |
9 |
Correct |
502 ms |
78688 KB |
Output is correct |
10 |
Correct |
662 ms |
78720 KB |
Output is correct |
11 |
Correct |
528 ms |
78664 KB |
Output is correct |
12 |
Correct |
90 ms |
78664 KB |
Output is correct |
13 |
Execution timed out |
1063 ms |
51912 KB |
Time limit exceeded |
14 |
Execution timed out |
1058 ms |
53832 KB |
Time limit exceeded |
15 |
Correct |
425 ms |
78516 KB |
Output is correct |
16 |
Correct |
370 ms |
78728 KB |
Output is correct |
17 |
Correct |
239 ms |
78672 KB |
Output is correct |
18 |
Correct |
101 ms |
78664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
233 ms |
79056 KB |
Output is correct |
2 |
Correct |
359 ms |
80664 KB |
Output is correct |
3 |
Execution timed out |
1056 ms |
33472 KB |
Time limit exceeded |
4 |
Correct |
474 ms |
78680 KB |
Output is correct |
5 |
Execution timed out |
1070 ms |
58816 KB |
Time limit exceeded |
6 |
Correct |
411 ms |
78664 KB |
Output is correct |
7 |
Correct |
250 ms |
78864 KB |
Output is correct |
8 |
Correct |
417 ms |
78752 KB |
Output is correct |
9 |
Execution timed out |
1075 ms |
47808 KB |
Time limit exceeded |
10 |
Execution timed out |
1043 ms |
33468 KB |
Time limit exceeded |
11 |
Execution timed out |
1064 ms |
36224 KB |
Time limit exceeded |
12 |
Correct |
858 ms |
78664 KB |
Output is correct |
13 |
Correct |
252 ms |
78664 KB |
Output is correct |
14 |
Correct |
485 ms |
78692 KB |
Output is correct |
15 |
Execution timed out |
1055 ms |
42444 KB |
Time limit exceeded |
16 |
Correct |
334 ms |
80832 KB |
Output is correct |
17 |
Execution timed out |
1068 ms |
50200 KB |
Time limit exceeded |
18 |
Execution timed out |
1060 ms |
49956 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1062 ms |
42576 KB |
Time limit exceeded |
2 |
Execution timed out |
1053 ms |
32352 KB |
Time limit exceeded |
3 |
Execution timed out |
1075 ms |
32300 KB |
Time limit exceeded |
4 |
Correct |
987 ms |
78960 KB |
Output is correct |
5 |
Correct |
415 ms |
80920 KB |
Output is correct |
6 |
Execution timed out |
1074 ms |
56268 KB |
Time limit exceeded |
7 |
Execution timed out |
1054 ms |
68460 KB |
Time limit exceeded |
8 |
Execution timed out |
1060 ms |
44560 KB |
Time limit exceeded |
9 |
Execution timed out |
1074 ms |
44576 KB |
Time limit exceeded |
10 |
Execution timed out |
1047 ms |
78936 KB |
Time limit exceeded |
11 |
Correct |
757 ms |
78916 KB |
Output is correct |
12 |
Execution timed out |
1059 ms |
58264 KB |
Time limit exceeded |
13 |
Execution timed out |
1075 ms |
40164 KB |
Time limit exceeded |
14 |
Correct |
786 ms |
79108 KB |
Output is correct |
15 |
Execution timed out |
1070 ms |
49992 KB |
Time limit exceeded |
16 |
Execution timed out |
1040 ms |
41800 KB |
Time limit exceeded |
17 |
Execution timed out |
1061 ms |
50680 KB |
Time limit exceeded |
18 |
Execution timed out |
1060 ms |
34360 KB |
Time limit exceeded |
19 |
Correct |
366 ms |
78764 KB |
Output is correct |
20 |
Execution timed out |
1067 ms |
34332 KB |
Time limit exceeded |
21 |
Execution timed out |
1065 ms |
78664 KB |
Time limit exceeded |
22 |
Execution timed out |
1052 ms |
37568 KB |
Time limit exceeded |
23 |
Correct |
384 ms |
79560 KB |
Output is correct |
24 |
Correct |
234 ms |
79040 KB |
Output is correct |
25 |
Execution timed out |
1049 ms |
78420 KB |
Time limit exceeded |
26 |
Correct |
999 ms |
78920 KB |
Output is correct |
27 |
Execution timed out |
1070 ms |
31492 KB |
Time limit exceeded |
28 |
Correct |
299 ms |
78920 KB |
Output is correct |
29 |
Execution timed out |
1072 ms |
47892 KB |
Time limit exceeded |
30 |
Execution timed out |
1068 ms |
56148 KB |
Time limit exceeded |
31 |
Correct |
398 ms |
78924 KB |
Output is correct |
32 |
Correct |
563 ms |
78920 KB |
Output is correct |
33 |
Correct |
152 ms |
78804 KB |
Output is correct |
34 |
Execution timed out |
1074 ms |
68340 KB |
Time limit exceeded |
35 |
Correct |
364 ms |
78920 KB |
Output is correct |
36 |
Execution timed out |
1076 ms |
39712 KB |
Time limit exceeded |
37 |
Correct |
413 ms |
81088 KB |
Output is correct |
38 |
Execution timed out |
1060 ms |
56280 KB |
Time limit exceeded |
39 |
Correct |
319 ms |
79084 KB |
Output is correct |
40 |
Execution timed out |
1076 ms |
62408 KB |
Time limit exceeded |
41 |
Execution timed out |
1049 ms |
66320 KB |
Time limit exceeded |
42 |
Execution timed out |
1063 ms |
45640 KB |
Time limit exceeded |