답안 #92639 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92639	2019-01-04T08:34:46 Z	luckyboy	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	10 / 100	1000 ms	39660 KB

brunhilda

/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int  i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int  i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 10000007
#define pii pair <int,int>
#define Task ""
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,q,a[maxn],tich = 1,dp[maxm];
int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n >> q;
    FOR(i,1,n)
    {
        cin >> a[i];
        if (1ll*tich*a[i] > 1e7)
        {
            tich = 1e7 + 1;
        }
        else tich *= a[i];
    }
    dp[0] = 0;
    FOR(i,1,tich - 1)
        {
            dp[i] = maxc;
            FOR(j,1,n)
            {
                int x = i / a[j];
                x *= a[j];
                dp[i] = min(dp[i],dp[x] + 1);
            }
        }
    while (q--)
    {
        int x;
        cin >> x;
        if (x >= tich)
        {
            cout << "oo\n";
        }
        else
        {
            cout << dp[x] << '\n';
        }
    }
    return 0;
}

Subtask #1
10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Execution timed out	1074 ms	27244 KB	Time limit exceeded
3	Correct	7 ms	1400 KB	Output is correct
4	Execution timed out	1081 ms	14308 KB	Time limit exceeded
5	Correct	404 ms	39608 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	7 ms	1400 KB	Output is correct
8	Correct	24 ms	3832 KB	Output is correct
9	Correct	401 ms	39660 KB	Output is correct
10	Correct	786 ms	39544 KB	Output is correct
11	Correct	771 ms	39496 KB	Output is correct
12	Execution timed out	1080 ms	11728 KB	Time limit exceeded
13	Execution timed out	1074 ms	1468 KB	Time limit exceeded
14	Execution timed out	1083 ms	1528 KB	Time limit exceeded
15	Execution timed out	1086 ms	37624 KB	Time limit exceeded
16	Execution timed out	1080 ms	27600 KB	Time limit exceeded
17	Execution timed out	1083 ms	22948 KB	Time limit exceeded
18	Execution timed out	1084 ms	14456 KB	Time limit exceeded

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1071 ms	668 KB	Time limit exceeded
2	Execution timed out	1079 ms	760 KB	Time limit exceeded
3	Execution timed out	1071 ms	760 KB	Time limit exceeded
4	Execution timed out	1078 ms	776 KB	Time limit exceeded
5	Execution timed out	1080 ms	632 KB	Time limit exceeded
6	Execution timed out	1070 ms	1396 KB	Time limit exceeded
7	Execution timed out	1079 ms	636 KB	Time limit exceeded
8	Execution timed out	1073 ms	1540 KB	Time limit exceeded
9	Execution timed out	1074 ms	888 KB	Time limit exceeded
10	Execution timed out	1077 ms	760 KB	Time limit exceeded
11	Execution timed out	1077 ms	604 KB	Time limit exceeded
12	Execution timed out	1083 ms	1236 KB	Time limit exceeded
13	Execution timed out	1083 ms	1016 KB	Time limit exceeded
14	Execution timed out	1080 ms	1028 KB	Time limit exceeded
15	Execution timed out	1083 ms	764 KB	Time limit exceeded
16	Execution timed out	1088 ms	760 KB	Time limit exceeded
17	Execution timed out	1069 ms	888 KB	Time limit exceeded
18	Execution timed out	1079 ms	760 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1077 ms	636 KB	Time limit exceeded
2	Execution timed out	1081 ms	632 KB	Time limit exceeded
3	Execution timed out	1089 ms	632 KB	Time limit exceeded
4	Execution timed out	1083 ms	1016 KB	Time limit exceeded
5	Execution timed out	1087 ms	888 KB	Time limit exceeded
6	Execution timed out	1089 ms	688 KB	Time limit exceeded
7	Execution timed out	1086 ms	888 KB	Time limit exceeded
8	Execution timed out	1079 ms	644 KB	Time limit exceeded
9	Execution timed out	1083 ms	636 KB	Time limit exceeded
10	Execution timed out	1080 ms	788 KB	Time limit exceeded
11	Execution timed out	1076 ms	696 KB	Time limit exceeded
12	Execution timed out	1072 ms	704 KB	Time limit exceeded
13	Execution timed out	1068 ms	760 KB	Time limit exceeded
14	Execution timed out	1085 ms	37752 KB	Time limit exceeded
15	Execution timed out	1071 ms	772 KB	Time limit exceeded
16	Execution timed out	1086 ms	760 KB	Time limit exceeded
17	Execution timed out	1078 ms	712 KB	Time limit exceeded
18	Execution timed out	1089 ms	724 KB	Time limit exceeded
19	Execution timed out	1081 ms	760 KB	Time limit exceeded
20	Execution timed out	1082 ms	632 KB	Time limit exceeded
21	Execution timed out	1076 ms	11660 KB	Time limit exceeded
22	Execution timed out	1068 ms	792 KB	Time limit exceeded
23	Execution timed out	1082 ms	692 KB	Time limit exceeded
24	Execution timed out	1071 ms	1600 KB	Time limit exceeded
25	Execution timed out	1071 ms	996 KB	Time limit exceeded
26	Execution timed out	1074 ms	880 KB	Time limit exceeded
27	Execution timed out	1086 ms	888 KB	Time limit exceeded
28	Execution timed out	1083 ms	1656 KB	Time limit exceeded
29	Execution timed out	1070 ms	760 KB	Time limit exceeded
30	Execution timed out	1087 ms	632 KB	Time limit exceeded
31	Execution timed out	1082 ms	888 KB	Time limit exceeded
32	Execution timed out	1081 ms	1016 KB	Time limit exceeded
33	Execution timed out	1074 ms	1400 KB	Time limit exceeded
34	Execution timed out	1075 ms	888 KB	Time limit exceeded
35	Execution timed out	1068 ms	1216 KB	Time limit exceeded
36	Execution timed out	1084 ms	760 KB	Time limit exceeded
37	Execution timed out	1071 ms	1016 KB	Time limit exceeded
38	Execution timed out	1076 ms	820 KB	Time limit exceeded
39	Execution timed out	1076 ms	1160 KB	Time limit exceeded
40	Execution timed out	1075 ms	632 KB	Time limit exceeded
41	Execution timed out	1077 ms	760 KB	Time limit exceeded
42	Execution timed out	1078 ms	900 KB	Time limit exceeded

답안 #92639

Compilation message

Subtask #1 10.0 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
10.0 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0