| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 155733 | 2019-09-30T07:17:16 Z | Flying_dragon_02 | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 149080 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int mod = 1e9 + 7;
const int inf = 1e9;
int add(int x, int y) {
return (1ll * x + 1ll * y) % mod;
}
int del(int x, int y) {
return ((1ll * x - 1ll * y) % mod + mod) % mod;
}
int mul(int x, int y) {
return (1ll * x * 1ll * y) % mod;
}
const int N = 1e7 + 5;
int dp[N], p[N];
int bit[2 * N];
void update(int x, int val) {
while(x > 0) {
bit[x] = min(bit[x], val);
x -= x & (-x);
}
}
int get(int x) {
if(x == 0) return 0;
int val = inf;
while(x < N) {
val = min(val, bit[x]);
x += x & (-x);
}
return val;
}
int m, q;
int main() {
scanf("%d%d", &m, &q);
for(int i = 0; i < N; i++)
p[i] = 0;
for(int i = 1; i <= N - 5; i++)
bit[i] = inf;
for(int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
for(int l = 0; l < N; l++) {
if(x * l >= N) break;
p[x * l] = max(p[x * l], x);
}
}
for(int i = 0; i <= N - 5; i++) {
dp[i] = get(i);
if(!p[i]) continue;
update(i + p[i] - 1, dp[i] + 1);
}
for(int i = 1; i <= q; i++) {
int x;
scanf("%d", &x);
if(dp[x] == inf)
printf("oo\n");
else
printf("%d\n", dp[x]);
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 477 ms | 117908 KB | Output is correct |
| 2 | Correct | 725 ms | 117848 KB | Output is correct |
| 3 | Correct | 646 ms | 117720 KB | Output is correct |
| 4 | Correct | 416 ms | 117812 KB | Output is correct |
| 5 | Correct | 540 ms | 117836 KB | Output is correct |
| 6 | Correct | 475 ms | 117744 KB | Output is correct |
| 7 | Correct | 635 ms | 117752 KB | Output is correct |
| 8 | Correct | 701 ms | 117880 KB | Output is correct |
| 9 | Correct | 747 ms | 117836 KB | Output is correct |
| 10 | Correct | 781 ms | 117816 KB | Output is correct |
| 11 | Correct | 734 ms | 117880 KB | Output is correct |
| 12 | Correct | 404 ms | 117856 KB | Output is correct |
| 13 | Correct | 922 ms | 118108 KB | Output is correct |
| 14 | Correct | 945 ms | 117788 KB | Output is correct |
| 15 | Correct | 702 ms | 117920 KB | Output is correct |
| 16 | Correct | 695 ms | 117912 KB | Output is correct |
| 17 | Correct | 550 ms | 117880 KB | Output is correct |
| 18 | Correct | 422 ms | 117876 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 556 ms | 121068 KB | Output is correct |
| 2 | Correct | 672 ms | 149060 KB | Output is correct |
| 3 | Execution timed out | 1078 ms | 113952 KB | Time limit exceeded |
| 4 | Correct | 649 ms | 118160 KB | Output is correct |
| 5 | Correct | 975 ms | 122780 KB | Output is correct |
| 6 | Correct | 650 ms | 118000 KB | Output is correct |
| 7 | Correct | 525 ms | 120952 KB | Output is correct |
| 8 | Correct | 609 ms | 117896 KB | Output is correct |
| 9 | Execution timed out | 1056 ms | 122816 KB | Time limit exceeded |
| 10 | Execution timed out | 1082 ms | 114200 KB | Time limit exceeded |
| 11 | Execution timed out | 1079 ms | 113680 KB | Time limit exceeded |
| 12 | Correct | 791 ms | 117956 KB | Output is correct |
| 13 | Correct | 537 ms | 119800 KB | Output is correct |
| 14 | Correct | 651 ms | 118232 KB | Output is correct |
| 15 | Execution timed out | 1057 ms | 120732 KB | Time limit exceeded |
| 16 | Correct | 679 ms | 149080 KB | Output is correct |
| 17 | Correct | 994 ms | 117916 KB | Output is correct |
| 18 | Execution timed out | 1083 ms | 123100 KB | Time limit exceeded |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1050 ms | 121828 KB | Time limit exceeded |
| 2 | Execution timed out | 1071 ms | 112908 KB | Time limit exceeded |
| 3 | Execution timed out | 1088 ms | 112060 KB | Time limit exceeded |
| 4 | Incorrect | 913 ms | 118396 KB | Output isn't correct |
| 5 | Incorrect | 710 ms | 131036 KB | Output isn't correct |
| 6 | Correct | 995 ms | 118556 KB | Output is correct |
| 7 | Execution timed out | 1026 ms | 125732 KB | Time limit exceeded |
| 8 | Execution timed out | 1065 ms | 121764 KB | Time limit exceeded |
| 9 | Execution timed out | 1056 ms | 118040 KB | Time limit exceeded |
| 10 | Correct | 837 ms | 118188 KB | Output is correct |
| 11 | Correct | 768 ms | 118436 KB | Output is correct |
| 12 | Correct | 922 ms | 118104 KB | Output is correct |
| 13 | Execution timed out | 1081 ms | 119552 KB | Time limit exceeded |
| 14 | Correct | 829 ms | 118384 KB | Output is correct |
| 15 | Correct | 958 ms | 118164 KB | Output is correct |
| 16 | Correct | 993 ms | 118156 KB | Output is correct |
| 17 | Correct | 990 ms | 120916 KB | Output is correct |
| 18 | Execution timed out | 1088 ms | 116788 KB | Time limit exceeded |
| 19 | Incorrect | 639 ms | 120288 KB | Output isn't correct |
| 20 | Execution timed out | 1079 ms | 115732 KB | Time limit exceeded |
| 21 | Incorrect | 914 ms | 118360 KB | Output isn't correct |
| 22 | Execution timed out | 1069 ms | 112832 KB | Time limit exceeded |
| 23 | Correct | 689 ms | 121884 KB | Output is correct |
| 24 | Correct | 540 ms | 118536 KB | Output is correct |
| 25 | Correct | 863 ms | 118276 KB | Output is correct |
| 26 | Incorrect | 858 ms | 118328 KB | Output isn't correct |
| 27 | Execution timed out | 1071 ms | 113600 KB | Time limit exceeded |
| 28 | Incorrect | 678 ms | 118512 KB | Output isn't correct |
| 29 | Execution timed out | 1082 ms | 114808 KB | Time limit exceeded |
| 30 | Execution timed out | 1066 ms | 121924 KB | Time limit exceeded |
| 31 | Correct | 675 ms | 119228 KB | Output is correct |
| 32 | Correct | 721 ms | 118384 KB | Output is correct |
| 33 | Correct | 483 ms | 118704 KB | Output is correct |
| 34 | Execution timed out | 1008 ms | 125748 KB | Time limit exceeded |
| 35 | Incorrect | 641 ms | 118404 KB | Output isn't correct |
| 36 | Execution timed out | 1047 ms | 116408 KB | Time limit exceeded |
| 37 | Incorrect | 683 ms | 131164 KB | Output isn't correct |
| 38 | Correct | 966 ms | 118712 KB | Output is correct |
| 39 | Correct | 586 ms | 118588 KB | Output is correct |
| 40 | Correct | 911 ms | 118768 KB | Output is correct |
| 41 | Correct | 967 ms | 130536 KB | Output is correct |
| 42 | Correct | 989 ms | 118336 KB | Output is correct |