#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i, a, b) for (int i=a;i>=b;--i)
const int MX_M = 1e5+5;
const int MX_Q = 1e5+5;
const int MX_P = 1e7+5;
int M, Q, P[MX_M];
int dp[MX_P];
using ii = pair<int, int>;
priority_queue<ii, vector<ii>, greater<ii> > pq;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> M >> Q;
FOR(i,1,M){
cin >> P[i];
pq.emplace(0,i);
}
const int infty = 1e9;
dp[0] = 0;
FOR(i,1,MX_P-1){
while (1) {
ii u = pq.top();
if (u.first + P[u.second] <= i) {
pq.pop();
pq.emplace(u.first + P[u.second], u.second);
} else break;
}
int j = pq.top().first;
if (j < i) dp[i] = min(infty, dp[j] + 1);
else dp[i] = infty;
}
FOR(i,1,Q){
int N; cin >> N;
if (dp[N] == infty) cout << "oo" << '\n';
else cout << dp[N] << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
103 ms |
39544 KB |
Output is correct |
| 2 |
Correct |
512 ms |
39540 KB |
Output is correct |
| 3 |
Correct |
362 ms |
39492 KB |
Output is correct |
| 4 |
Correct |
98 ms |
39544 KB |
Output is correct |
| 5 |
Correct |
184 ms |
39544 KB |
Output is correct |
| 6 |
Correct |
106 ms |
39424 KB |
Output is correct |
| 7 |
Correct |
361 ms |
39460 KB |
Output is correct |
| 8 |
Correct |
427 ms |
39544 KB |
Output is correct |
| 9 |
Correct |
668 ms |
39552 KB |
Output is correct |
| 10 |
Correct |
870 ms |
39628 KB |
Output is correct |
| 11 |
Correct |
639 ms |
39544 KB |
Output is correct |
| 12 |
Correct |
77 ms |
39416 KB |
Output is correct |
| 13 |
Execution timed out |
1097 ms |
19448 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1095 ms |
18680 KB |
Time limit exceeded |
| 15 |
Correct |
536 ms |
39520 KB |
Output is correct |
| 16 |
Correct |
534 ms |
39468 KB |
Output is correct |
| 17 |
Correct |
236 ms |
39544 KB |
Output is correct |
| 18 |
Correct |
95 ms |
39544 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
266 ms |
39872 KB |
Output is correct |
| 2 |
Correct |
224 ms |
41400 KB |
Output is correct |
| 3 |
Execution timed out |
1095 ms |
21168 KB |
Time limit exceeded |
| 4 |
Correct |
575 ms |
39548 KB |
Output is correct |
| 5 |
Execution timed out |
1097 ms |
29224 KB |
Time limit exceeded |
| 6 |
Correct |
567 ms |
39492 KB |
Output is correct |
| 7 |
Correct |
250 ms |
39800 KB |
Output is correct |
| 8 |
Correct |
448 ms |
39544 KB |
Output is correct |
| 9 |
Execution timed out |
1096 ms |
23844 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1099 ms |
21232 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1084 ms |
15476 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1096 ms |
37752 KB |
Time limit exceeded |
| 13 |
Correct |
245 ms |
39544 KB |
Output is correct |
| 14 |
Correct |
549 ms |
39704 KB |
Output is correct |
| 15 |
Execution timed out |
1099 ms |
20036 KB |
Time limit exceeded |
| 16 |
Correct |
210 ms |
41456 KB |
Output is correct |
| 17 |
Execution timed out |
1097 ms |
17680 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1093 ms |
25876 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1093 ms |
20792 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1096 ms |
15416 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1095 ms |
16756 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1088 ms |
33992 KB |
Time limit exceeded |
| 5 |
Correct |
343 ms |
42476 KB |
Output is correct |
| 6 |
Execution timed out |
1100 ms |
20728 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1095 ms |
38316 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1097 ms |
20980 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1096 ms |
20852 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1094 ms |
32504 KB |
Time limit exceeded |
| 11 |
Correct |
995 ms |
39928 KB |
Output is correct |
| 12 |
Execution timed out |
1093 ms |
21192 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1074 ms |
16760 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1014 ms |
40824 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1098 ms |
18552 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1097 ms |
16248 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1091 ms |
23832 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1095 ms |
15868 KB |
Time limit exceeded |
| 19 |
Correct |
419 ms |
39928 KB |
Output is correct |
| 20 |
Execution timed out |
1094 ms |
16884 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1087 ms |
30112 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1098 ms |
20204 KB |
Time limit exceeded |
| 23 |
Correct |
444 ms |
41208 KB |
Output is correct |
| 24 |
Correct |
246 ms |
40664 KB |
Output is correct |
| 25 |
Execution timed out |
1098 ms |
30840 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1094 ms |
34296 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1098 ms |
17904 KB |
Time limit exceeded |
| 28 |
Correct |
363 ms |
40696 KB |
Output is correct |
| 29 |
Execution timed out |
1097 ms |
25456 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1097 ms |
25924 KB |
Time limit exceeded |
| 31 |
Correct |
470 ms |
40696 KB |
Output is correct |
| 32 |
Correct |
672 ms |
40568 KB |
Output is correct |
| 33 |
Correct |
157 ms |
40440 KB |
Output is correct |
| 34 |
Execution timed out |
1097 ms |
37612 KB |
Time limit exceeded |
| 35 |
Correct |
449 ms |
40568 KB |
Output is correct |
| 36 |
Execution timed out |
1099 ms |
20080 KB |
Time limit exceeded |
| 37 |
Correct |
338 ms |
42604 KB |
Output is correct |
| 38 |
Execution timed out |
1087 ms |
20600 KB |
Time limit exceeded |
| 39 |
Correct |
340 ms |
40568 KB |
Output is correct |
| 40 |
Execution timed out |
1094 ms |
25976 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1097 ms |
41328 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1096 ms |
16504 KB |
Time limit exceeded |
