| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 134092 | 2019-07-22T04:18:44 Z | wilwxk | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 802 ms | 40316 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MAXX=1e7+3;
const int INF=1e9;
int v[MAXN];
int dp[MAXX];
int n, q;
int main() {
scanf("%d %d", &n, &q);
for(int i=0; i<n; i++) scanf("%d", &v[i]);
dp[0]=0;
for(int i=1; i<v[n-1]; i++) dp[i]=1;
for(int i=v[n-1]; i<MAXX; i++) {
dp[i]=INF;
bool ok=0;
for(int j=n-1; j>=max(0, n-15); j--) {
if(i%v[j]==0) continue;
int ind=i-(i%v[j]);
dp[i]=min(dp[i], dp[ind]+1);
}
}
// for(int i=0; i<MAXX; i++) printf("%d ", dp[i]);
while(q--) {
int a; scanf("%d", &a);
if(dp[a]==-1||dp[a]>MAXN) printf("oo\n");
else printf("%d\n", dp[a]);
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 219 ms | 39416 KB | Output is correct |
| 2 | Correct | 724 ms | 39544 KB | Output is correct |
| 3 | Correct | 305 ms | 39544 KB | Output is correct |
| 4 | Incorrect | 718 ms | 39544 KB | Output isn't correct |
| 5 | Correct | 556 ms | 39524 KB | Output is correct |
| 6 | Correct | 211 ms | 39420 KB | Output is correct |
| 7 | Correct | 306 ms | 39564 KB | Output is correct |
| 8 | Correct | 355 ms | 39544 KB | Output is correct |
| 9 | Correct | 666 ms | 39548 KB | Output is correct |
| 10 | Correct | 802 ms | 39416 KB | Output is correct |
| 11 | Correct | 786 ms | 39520 KB | Output is correct |
| 12 | Correct | 715 ms | 39516 KB | Output is correct |
| 13 | Correct | 715 ms | 39404 KB | Output is correct |
| 14 | Correct | 717 ms | 39524 KB | Output is correct |
| 15 | Correct | 728 ms | 39492 KB | Output is correct |
| 16 | Correct | 737 ms | 39548 KB | Output is correct |
| 17 | Correct | 726 ms | 39608 KB | Output is correct |
| 18 | Incorrect | 716 ms | 39544 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 663 ms | 39480 KB | Output is correct |
| 2 | Correct | 118 ms | 39904 KB | Output is correct |
| 3 | Correct | 555 ms | 39736 KB | Output is correct |
| 4 | Incorrect | 711 ms | 39608 KB | Output isn't correct |
| 5 | Correct | 635 ms | 39640 KB | Output is correct |
| 6 | Incorrect | 712 ms | 39408 KB | Output isn't correct |
| 7 | Correct | 654 ms | 39480 KB | Output is correct |
| 8 | Incorrect | 714 ms | 39480 KB | Output isn't correct |
| 9 | Correct | 636 ms | 39776 KB | Output is correct |
| 10 | Correct | 554 ms | 39672 KB | Output is correct |
| 11 | Incorrect | 659 ms | 39616 KB | Output isn't correct |
| 12 | Incorrect | 710 ms | 39476 KB | Output isn't correct |
| 13 | Incorrect | 693 ms | 39468 KB | Output isn't correct |
| 14 | Incorrect | 708 ms | 39432 KB | Output isn't correct |
| 15 | Correct | 677 ms | 39620 KB | Output is correct |
| 16 | Correct | 118 ms | 39804 KB | Output is correct |
| 17 | Correct | 718 ms | 39468 KB | Output is correct |
| 18 | Incorrect | 391 ms | 39964 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 675 ms | 39704 KB | Output is correct |
| 2 | Correct | 712 ms | 39712 KB | Output is correct |
| 3 | Correct | 674 ms | 39860 KB | Output is correct |
| 4 | Incorrect | 753 ms | 39812 KB | Output isn't correct |
| 5 | Correct | 463 ms | 40056 KB | Output is correct |
| 6 | Incorrect | 742 ms | 39732 KB | Output isn't correct |
| 7 | Correct | 559 ms | 39928 KB | Output is correct |
| 8 | Correct | 669 ms | 39888 KB | Output is correct |
| 9 | Correct | 711 ms | 39756 KB | Output is correct |
| 10 | Incorrect | 738 ms | 39560 KB | Output isn't correct |
| 11 | Incorrect | 717 ms | 39672 KB | Output isn't correct |
| 12 | Incorrect | 718 ms | 39644 KB | Output isn't correct |
| 13 | Incorrect | 706 ms | 40028 KB | Output isn't correct |
| 14 | Correct | 785 ms | 40112 KB | Output is correct |
| 15 | Incorrect | 720 ms | 39800 KB | Output isn't correct |
| 16 | Incorrect | 720 ms | 39680 KB | Output isn't correct |
| 17 | Correct | 672 ms | 39856 KB | Output is correct |
| 18 | Correct | 685 ms | 39800 KB | Output is correct |
| 19 | Correct | 678 ms | 39624 KB | Output is correct |
| 20 | Correct | 668 ms | 39908 KB | Output is correct |
| 21 | Incorrect | 745 ms | 40316 KB | Output isn't correct |
| 22 | Correct | 663 ms | 40284 KB | Output is correct |
| 23 | Correct | 689 ms | 39816 KB | Output is correct |
| 24 | Incorrect | 754 ms | 39784 KB | Output isn't correct |
| 25 | Incorrect | 750 ms | 39876 KB | Output isn't correct |
| 26 | Incorrect | 749 ms | 39824 KB | Output isn't correct |
| 27 | Correct | 632 ms | 40160 KB | Output is correct |
| 28 | Incorrect | 743 ms | 39912 KB | Output isn't correct |
| 29 | Correct | 683 ms | 40028 KB | Output is correct |
| 30 | Correct | 708 ms | 40100 KB | Output is correct |
| 31 | Incorrect | 730 ms | 39832 KB | Output isn't correct |
| 32 | Incorrect | 756 ms | 39984 KB | Output isn't correct |
| 33 | Incorrect | 743 ms | 39800 KB | Output isn't correct |
| 34 | Correct | 552 ms | 40012 KB | Output is correct |
| 35 | Incorrect | 732 ms | 39832 KB | Output isn't correct |
| 36 | Correct | 683 ms | 40244 KB | Output is correct |
| 37 | Correct | 467 ms | 40056 KB | Output is correct |
| 38 | Incorrect | 742 ms | 39884 KB | Output isn't correct |
| 39 | Incorrect | 770 ms | 39872 KB | Output isn't correct |
| 40 | Incorrect | 750 ms | 39928 KB | Output isn't correct |
| 41 | Correct | 243 ms | 39928 KB | Output is correct |
| 42 | Incorrect | 768 ms | 39916 KB | Output isn't correct |