| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 134087 | 2019-07-22T04:15:08 Z | wilwxk | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 40864 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-20); 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 | 212 ms | 39484 KB | Output is correct |
| 2 | Correct | 962 ms | 39564 KB | Output is correct |
| 3 | Correct | 306 ms | 39500 KB | Output is correct |
| 4 | Incorrect | 936 ms | 39636 KB | Output isn't correct |
| 5 | Correct | 552 ms | 39428 KB | Output is correct |
| 6 | Correct | 212 ms | 39416 KB | Output is correct |
| 7 | Correct | 306 ms | 39440 KB | Output is correct |
| 8 | Correct | 354 ms | 39416 KB | Output is correct |
| 9 | Correct | 665 ms | 39456 KB | Output is correct |
| 10 | Execution timed out | 1065 ms | 34072 KB | Time limit exceeded |
| 11 | Execution timed out | 1054 ms | 35252 KB | Time limit exceeded |
| 12 | Correct | 936 ms | 39452 KB | Output is correct |
| 13 | Correct | 937 ms | 39524 KB | Output is correct |
| 14 | Correct | 936 ms | 39528 KB | Output is correct |
| 15 | Correct | 965 ms | 39608 KB | Output is correct |
| 16 | Correct | 967 ms | 39420 KB | Output is correct |
| 17 | Correct | 952 ms | 39524 KB | Output is correct |
| 18 | Incorrect | 941 ms | 39580 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 870 ms | 39432 KB | Output is correct |
| 2 | Correct | 140 ms | 39884 KB | Output is correct |
| 3 | Correct | 731 ms | 39760 KB | Output is correct |
| 4 | Incorrect | 927 ms | 39484 KB | Output isn't correct |
| 5 | Correct | 828 ms | 39636 KB | Output is correct |
| 6 | Correct | 931 ms | 39604 KB | Output is correct |
| 7 | Correct | 861 ms | 39608 KB | Output is correct |
| 8 | Incorrect | 939 ms | 39552 KB | Output isn't correct |
| 9 | Correct | 831 ms | 39800 KB | Output is correct |
| 10 | Correct | 737 ms | 39856 KB | Output is correct |
| 11 | Incorrect | 868 ms | 39704 KB | Output isn't correct |
| 12 | Incorrect | 936 ms | 39584 KB | Output isn't correct |
| 13 | Correct | 897 ms | 39544 KB | Output is correct |
| 14 | Incorrect | 931 ms | 39584 KB | Output isn't correct |
| 15 | Correct | 902 ms | 39640 KB | Output is correct |
| 16 | Correct | 138 ms | 39940 KB | Output is correct |
| 17 | Correct | 931 ms | 39540 KB | Output is correct |
| 18 | Incorrect | 506 ms | 39908 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 877 ms | 40052 KB | Output is correct |
| 2 | Correct | 893 ms | 39836 KB | Output is correct |
| 3 | Correct | 884 ms | 40312 KB | Output is correct |
| 4 | Incorrect | 972 ms | 40368 KB | Output isn't correct |
| 5 | Correct | 587 ms | 40268 KB | Output is correct |
| 6 | Incorrect | 964 ms | 40568 KB | Output isn't correct |
| 7 | Correct | 719 ms | 39968 KB | Output is correct |
| 8 | Correct | 873 ms | 39808 KB | Output is correct |
| 9 | Correct | 869 ms | 39940 KB | Output is correct |
| 10 | Incorrect | 934 ms | 39520 KB | Output isn't correct |
| 11 | Incorrect | 943 ms | 39756 KB | Output isn't correct |
| 12 | Incorrect | 935 ms | 39704 KB | Output isn't correct |
| 13 | Incorrect | 891 ms | 39884 KB | Output isn't correct |
| 14 | Execution timed out | 1033 ms | 40724 KB | Time limit exceeded |
| 15 | Incorrect | 948 ms | 39656 KB | Output isn't correct |
| 16 | Incorrect | 938 ms | 39672 KB | Output isn't correct |
| 17 | Correct | 878 ms | 39612 KB | Output is correct |
| 18 | Correct | 901 ms | 39828 KB | Output is correct |
| 19 | Correct | 902 ms | 39664 KB | Output is correct |
| 20 | Correct | 873 ms | 39816 KB | Output is correct |
| 21 | Correct | 970 ms | 40864 KB | Output is correct |
| 22 | Correct | 865 ms | 40104 KB | Output is correct |
| 23 | Correct | 915 ms | 40476 KB | Output is correct |
| 24 | Incorrect | 982 ms | 40520 KB | Output isn't correct |
| 25 | Incorrect | 980 ms | 40420 KB | Output isn't correct |
| 26 | Incorrect | 963 ms | 40276 KB | Output isn't correct |
| 27 | Correct | 825 ms | 40088 KB | Output is correct |
| 28 | Incorrect | 945 ms | 40500 KB | Output isn't correct |
| 29 | Correct | 849 ms | 40012 KB | Output is correct |
| 30 | Correct | 903 ms | 40220 KB | Output is correct |
| 31 | Incorrect | 950 ms | 40208 KB | Output isn't correct |
| 32 | Incorrect | 968 ms | 40292 KB | Output isn't correct |
| 33 | Incorrect | 954 ms | 40332 KB | Output isn't correct |
| 34 | Correct | 718 ms | 39892 KB | Output is correct |
| 35 | Incorrect | 950 ms | 40444 KB | Output isn't correct |
| 36 | Correct | 859 ms | 39988 KB | Output is correct |
| 37 | Correct | 588 ms | 40024 KB | Output is correct |
| 38 | Incorrect | 962 ms | 40208 KB | Output isn't correct |
| 39 | Incorrect | 960 ms | 40420 KB | Output isn't correct |
| 40 | Incorrect | 960 ms | 40348 KB | Output isn't correct |
| 41 | Correct | 300 ms | 39992 KB | Output is correct |
| 42 | Incorrect | 957 ms | 40540 KB | Output isn't correct |