답안 #155746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155746	2019-09-30T08:25:16 Z	Flying_dragon_02	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	56.0317 / 100	1000 ms	157648 KB

brunhilda

#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 < 2 * 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 < 2 * N; 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

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
brunhilda.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	534 ms	156796 KB	Output is correct
2	Correct	770 ms	156824 KB	Output is correct
3	Correct	706 ms	156856 KB	Output is correct
4	Correct	483 ms	156916 KB	Output is correct
5	Correct	595 ms	156832 KB	Output is correct
6	Correct	536 ms	156796 KB	Output is correct
7	Correct	708 ms	156792 KB	Output is correct
8	Correct	796 ms	156916 KB	Output is correct
9	Correct	830 ms	156900 KB	Output is correct
10	Correct	881 ms	156836 KB	Output is correct
11	Correct	808 ms	157032 KB	Output is correct
12	Correct	457 ms	156856 KB	Output is correct
13	Execution timed out	1002 ms	156864 KB	Time limit exceeded
14	Execution timed out	1028 ms	156896 KB	Time limit exceeded
15	Correct	782 ms	156832 KB	Output is correct
16	Correct	766 ms	156920 KB	Output is correct
17	Correct	604 ms	156892 KB	Output is correct
18	Correct	508 ms	156956 KB	Output is correct

Subtask #2
11.1111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	609 ms	156892 KB	Output is correct
2	Correct	740 ms	156920 KB	Output is correct
3	Execution timed out	1069 ms	148476 KB	Time limit exceeded
4	Correct	738 ms	156984 KB	Output is correct
5	Execution timed out	1058 ms	156960 KB	Time limit exceeded
6	Correct	713 ms	157020 KB	Output is correct
7	Correct	587 ms	156960 KB	Output is correct
8	Correct	679 ms	156920 KB	Output is correct
9	Execution timed out	1077 ms	156200 KB	Time limit exceeded
10	Execution timed out	1081 ms	151484 KB	Time limit exceeded
11	Execution timed out	1082 ms	152652 KB	Time limit exceeded
12	Correct	873 ms	156932 KB	Output is correct
13	Correct	595 ms	156876 KB	Output is correct
14	Correct	716 ms	156872 KB	Output is correct
15	Execution timed out	1079 ms	156664 KB	Time limit exceeded
16	Correct	690 ms	157036 KB	Output is correct
17	Execution timed out	1016 ms	157052 KB	Time limit exceeded
18	Execution timed out	1082 ms	154680 KB	Time limit exceeded

Subtask #3
27.1428571429 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1071 ms	155268 KB	Time limit exceeded
2	Execution timed out	1081 ms	153632 KB	Time limit exceeded
3	Execution timed out	1072 ms	152688 KB	Time limit exceeded
4	Correct	922 ms	157236 KB	Output is correct
5	Correct	740 ms	157148 KB	Output is correct
6	Execution timed out	1041 ms	157192 KB	Time limit exceeded
7	Execution timed out	1097 ms	155748 KB	Time limit exceeded
8	Execution timed out	1098 ms	155036 KB	Time limit exceeded
9	Execution timed out	1087 ms	154736 KB	Time limit exceeded
10	Correct	916 ms	156944 KB	Output is correct
11	Correct	845 ms	157000 KB	Output is correct
12	Execution timed out	1008 ms	156924 KB	Time limit exceeded
13	Execution timed out	1087 ms	156184 KB	Time limit exceeded
14	Correct	914 ms	157572 KB	Output is correct
15	Execution timed out	1022 ms	157004 KB	Time limit exceeded
16	Execution timed out	1089 ms	157048 KB	Time limit exceeded
17	Execution timed out	1088 ms	156664 KB	Time limit exceeded
18	Execution timed out	1071 ms	148560 KB	Time limit exceeded
19	Correct	687 ms	156932 KB	Output is correct
20	Execution timed out	1090 ms	150680 KB	Time limit exceeded
21	Correct	947 ms	157648 KB	Output is correct
22	Execution timed out	1100 ms	151652 KB	Time limit exceeded
23	Correct	755 ms	157184 KB	Output is correct
24	Correct	597 ms	157324 KB	Output is correct
25	Correct	924 ms	157412 KB	Output is correct
26	Correct	925 ms	157300 KB	Output is correct
27	Execution timed out	1084 ms	147124 KB	Time limit exceeded
28	Correct	684 ms	157372 KB	Output is correct
29	Execution timed out	1089 ms	148652 KB	Time limit exceeded
30	Execution timed out	1072 ms	153108 KB	Time limit exceeded
31	Correct	737 ms	157176 KB	Output is correct
32	Correct	805 ms	157304 KB	Output is correct
33	Correct	540 ms	157268 KB	Output is correct
34	Execution timed out	1051 ms	157176 KB	Time limit exceeded
35	Correct	703 ms	157316 KB	Output is correct
36	Execution timed out	1078 ms	150316 KB	Time limit exceeded
37	Correct	739 ms	157224 KB	Output is correct
38	Execution timed out	1079 ms	157096 KB	Time limit exceeded
39	Correct	648 ms	157176 KB	Output is correct
40	Correct	988 ms	157116 KB	Output is correct
41	Execution timed out	1034 ms	157048 KB	Time limit exceeded
42	Execution timed out	1066 ms	157316 KB	Time limit exceeded

답안 #155746

Compilation message

Subtask #1 17.7777777778 / 20.0

Subtask #2 11.1111111111 / 20.0

Subtask #3 27.1428571429 / 60.0

Subtask #1
17.7777777778 / 20.0

Subtask #2
11.1111111111 / 20.0

Subtask #3
27.1428571429 / 60.0