| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256326 | 2020-08-02T14:29:33 Z | Saboon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 400 ms | 80760 KB |
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
const int maxn = 1e7 + 10;
int r[maxn], dp[maxn];
bitset<maxn> mark;
int main(){
ios_base::sync_with_stdio(false);
int m, q;
scanf("%d%d", &m, &q);
int n = 10*1000*1000;
while (m --){
int x;
scanf("%d", &x);
if (mark[x])
continue;
mark[x] = 1;
for (int i = 0; i <= n; i += x)
r[i] = max(r[i], i+x);
}
for (int i = 1; i <= n; i++)
r[i] = max(r[i], r[i-1]);
int mxm = n+1;
int last = 0;
for (int i = 1; i <= n; i++){
if (r[last] <= i)
last = i-1;
if (r[last] == i){
mxm = i;
break;
}
dp[i] = dp[last] + 1;
}
while (q --){
int x;
scanf("%d", &x);
if (x >= mxm)
printf("oo\n");
else
printf("%d\n", dp[x]);
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 77 ms | 39544 KB | Output is correct |
| 2 | Correct | 128 ms | 78584 KB | Output is correct |
| 3 | Correct | 87 ms | 40568 KB | Output is correct |
| 4 | Correct | 106 ms | 78712 KB | Output is correct |
| 5 | Correct | 126 ms | 78572 KB | Output is correct |
| 6 | Correct | 71 ms | 39544 KB | Output is correct |
| 7 | Correct | 97 ms | 40568 KB | Output is correct |
| 8 | Correct | 108 ms | 43000 KB | Output is correct |
| 9 | Correct | 146 ms | 78584 KB | Output is correct |
| 10 | Correct | 174 ms | 78580 KB | Output is correct |
| 11 | Correct | 166 ms | 78580 KB | Output is correct |
| 12 | Correct | 119 ms | 78584 KB | Output is correct |
| 13 | Correct | 297 ms | 78584 KB | Output is correct |
| 14 | Correct | 282 ms | 78840 KB | Output is correct |
| 15 | Correct | 149 ms | 78584 KB | Output is correct |
| 16 | Correct | 141 ms | 78588 KB | Output is correct |
| 17 | Correct | 160 ms | 78712 KB | Output is correct |
| 18 | Correct | 102 ms | 78720 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 126 ms | 78840 KB | Output is correct |
| 2 | Correct | 154 ms | 79864 KB | Output is correct |
| 3 | Correct | 286 ms | 78840 KB | Output is correct |
| 4 | Correct | 130 ms | 78584 KB | Output is correct |
| 5 | Correct | 255 ms | 78840 KB | Output is correct |
| 6 | Correct | 133 ms | 78712 KB | Output is correct |
| 7 | Correct | 115 ms | 78840 KB | Output is correct |
| 8 | Correct | 134 ms | 78584 KB | Output is correct |
| 9 | Correct | 252 ms | 78844 KB | Output is correct |
| 10 | Correct | 307 ms | 78832 KB | Output is correct |
| 11 | Correct | 285 ms | 78712 KB | Output is correct |
| 12 | Correct | 209 ms | 78584 KB | Output is correct |
| 13 | Correct | 118 ms | 78712 KB | Output is correct |
| 14 | Correct | 153 ms | 78584 KB | Output is correct |
| 15 | Correct | 320 ms | 78840 KB | Output is correct |
| 16 | Correct | 162 ms | 79864 KB | Output is correct |
| 17 | Correct | 290 ms | 78584 KB | Output is correct |
| 18 | Correct | 296 ms | 79096 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 305 ms | 79096 KB | Output is correct |
| 2 | Correct | 336 ms | 78968 KB | Output is correct |
| 3 | Correct | 316 ms | 79352 KB | Output is correct |
| 4 | Correct | 214 ms | 79352 KB | Output is correct |
| 5 | Correct | 173 ms | 79736 KB | Output is correct |
| 6 | Correct | 312 ms | 79224 KB | Output is correct |
| 7 | Correct | 285 ms | 79352 KB | Output is correct |
| 8 | Correct | 291 ms | 79100 KB | Output is correct |
| 9 | Correct | 295 ms | 79096 KB | Output is correct |
| 10 | Correct | 215 ms | 78840 KB | Output is correct |
| 11 | Correct | 202 ms | 78840 KB | Output is correct |
| 12 | Correct | 271 ms | 78840 KB | Output is correct |
| 13 | Correct | 365 ms | 79228 KB | Output is correct |
| 14 | Correct | 229 ms | 79612 KB | Output is correct |
| 15 | Correct | 233 ms | 78840 KB | Output is correct |
| 16 | Correct | 275 ms | 78968 KB | Output is correct |
| 17 | Correct | 231 ms | 78972 KB | Output is correct |
| 18 | Correct | 295 ms | 78968 KB | Output is correct |
| 19 | Correct | 117 ms | 78840 KB | Output is correct |
| 20 | Correct | 307 ms | 79096 KB | Output is correct |
| 21 | Correct | 215 ms | 79484 KB | Output is correct |
| 22 | Correct | 354 ms | 79264 KB | Output is correct |
| 23 | Correct | 179 ms | 79144 KB | Output is correct |
| 24 | Correct | 153 ms | 79096 KB | Output is correct |
| 25 | Correct | 227 ms | 79096 KB | Output is correct |
| 26 | Correct | 207 ms | 78976 KB | Output is correct |
| 27 | Correct | 331 ms | 79460 KB | Output is correct |
| 28 | Correct | 157 ms | 79164 KB | Output is correct |
| 29 | Correct | 400 ms | 79224 KB | Output is correct |
| 30 | Correct | 322 ms | 79368 KB | Output is correct |
| 31 | Correct | 229 ms | 79352 KB | Output is correct |
| 32 | Correct | 179 ms | 79696 KB | Output is correct |
| 33 | Correct | 148 ms | 79736 KB | Output is correct |
| 34 | Correct | 251 ms | 80248 KB | Output is correct |
| 35 | Correct | 155 ms | 79784 KB | Output is correct |
| 36 | Correct | 379 ms | 80336 KB | Output is correct |
| 37 | Correct | 179 ms | 80760 KB | Output is correct |
| 38 | Correct | 268 ms | 79736 KB | Output is correct |
| 39 | Correct | 154 ms | 79736 KB | Output is correct |
| 40 | Correct | 235 ms | 79704 KB | Output is correct |
| 41 | Correct | 226 ms | 80376 KB | Output is correct |
| 42 | Correct | 283 ms | 79864 KB | Output is correct |