oj.uz

Submission #155728

# Submission time Handle Problem Language Result Execution time Memory
155728 2019-09-30T06:54:21 Z souhhcong Brunhilda’s Birthday (BOI13_brunhilda) C++14
23.6508 / 100
 1000 ms 212472 KB 
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1e5+5, MAXN = 1e7+7, INF = 1e9+9;
int n, q, x, p[N], dp[MAXN], mx = 0;

int solve(int x)
{
    //cout << x << endl;
    if (dp[x] != -1)
        return dp[x];
    int mn = INF;
    for (int i = 0; i < n; i++)
    {
        if (!(x-x/p[i]*p[i])) continue;
        mn = min(mn,solve(x/p[i]*p[i])+1);
    }
    dp[x] = mn;
    return dp[x];
}

int main()
{
    memset(dp,-1,sizeof dp);
    scanf("%d %d",&n,&q);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&p[i]);
        mx = max(mx,p[i]);
    }
    for (int i = 1; i < mx; i++)
        dp[i] = 1;
    while(q--)
    {
        scanf("%d",&x);
        solve(x);
        if (dp[x] == INF) printf("oo\n");
        else printf("%d\n",dp[x]);
    }
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 39484 KB Output is correct
2 Correct 36 ms 39416 KB Output is correct
3 Correct 35 ms 39544 KB Output is correct
4 Correct 40 ms 39416 KB Output is correct
5 Correct 35 ms 39416 KB Output is correct
6 Correct 35 ms 39548 KB Output is correct
7 Correct 35 ms 39544 KB Output is correct
8 Correct 35 ms 39544 KB Output is correct
9 Correct 35 ms 39416 KB Output is correct
10 Correct 36 ms 39544 KB Output is correct
11 Correct 36 ms 39676 KB Output is correct
12 Correct 35 ms 39444 KB Output is correct
13 Correct 41 ms 39544 KB Output is correct
14 Correct 37 ms 39416 KB Output is correct
15 Correct 36 ms 39416 KB Output is correct
16 Correct 36 ms 39412 KB Output is correct
17 Correct 46 ms 39516 KB Output is correct
18 Correct 39 ms 39416 KB Output is correct

Subtask #2
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 41976 KB Time limit exceeded
2 Correct 62 ms 39800 KB Output is correct
3 Execution timed out 1079 ms 78752 KB Time limit exceeded
4 Execution timed out 1078 ms 60408 KB Time limit exceeded
5 Execution timed out 1085 ms 52088 KB Time limit exceeded
6 Execution timed out 1088 ms 47096 KB Time limit exceeded
7 Execution timed out 1086 ms 41976 KB Time limit exceeded
8 Execution timed out 1074 ms 47608 KB Time limit exceeded
9 Execution timed out 1074 ms 48888 KB Time limit exceeded
10 Execution timed out 1085 ms 78712 KB Time limit exceeded
11 Execution timed out 1101 ms 197880 KB Time limit exceeded
12 Execution timed out 1083 ms 89464 KB Time limit exceeded
13 Execution timed out 1083 ms 60664 KB Time limit exceeded
14 Execution timed out 1083 ms 60408 KB Time limit exceeded
15 Execution timed out 1077 ms 71800 KB Time limit exceeded
16 Correct 55 ms 39972 KB Output is correct
17 Execution timed out 1084 ms 210324 KB Time limit exceeded
18 Execution timed out 1073 ms 97784 KB Time limit exceeded

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 181908 KB Time limit exceeded
2 Execution timed out 1084 ms 175764 KB Time limit exceeded
3 Execution timed out 1095 ms 145272 KB Time limit exceeded
4 Execution timed out 1066 ms 111352 KB Time limit exceeded
5 Execution timed out 1065 ms 40056 KB Time limit exceeded
6 Execution timed out 1090 ms 150264 KB Time limit exceeded
7 Execution timed out 1071 ms 53752 KB Time limit exceeded
8 Execution timed out 1095 ms 181924 KB Time limit exceeded
9 Execution timed out 1082 ms 181996 KB Time limit exceeded
10 Execution timed out 1081 ms 44152 KB Time limit exceeded
11 Execution timed out 1057 ms 68856 KB Time limit exceeded
12 Execution timed out 1077 ms 124664 KB Time limit exceeded
13 Execution timed out 1080 ms 88568 KB Time limit exceeded
14 Execution timed out 1081 ms 143356 KB Time limit exceeded
15 Execution timed out 1087 ms 204024 KB Time limit exceeded
16 Execution timed out 1058 ms 136440 KB Time limit exceeded
17 Execution timed out 1066 ms 46328 KB Time limit exceeded
18 Execution timed out 1096 ms 175736 KB Time limit exceeded
19 Execution timed out 1072 ms 47400 KB Time limit exceeded
20 Execution timed out 1083 ms 145244 KB Time limit exceeded
21 Execution timed out 1080 ms 212472 KB Time limit exceeded
22 Execution timed out 1077 ms 138008 KB Time limit exceeded
23 Execution timed out 1080 ms 40056 KB Time limit exceeded
24 Execution timed out 1087 ms 45176 KB Time limit exceeded
25 Execution timed out 1074 ms 43256 KB Time limit exceeded
26 Execution timed out 1083 ms 111224 KB Time limit exceeded
27 Execution timed out 1089 ms 133624 KB Time limit exceeded
28 Execution timed out 1086 ms 71032 KB Time limit exceeded
29 Execution timed out 1084 ms 69624 KB Time limit exceeded
30 Execution timed out 1086 ms 56828 KB Time limit exceeded
31 Execution timed out 1077 ms 61948 KB Time limit exceeded
32 Execution timed out 1087 ms 64632 KB Time limit exceeded
33 Execution timed out 1064 ms 45304 KB Time limit exceeded
34 Execution timed out 1068 ms 53752 KB Time limit exceeded
35 Execution timed out 1071 ms 49488 KB Time limit exceeded
36 Execution timed out 1085 ms 148052 KB Time limit exceeded
37 Execution timed out 1082 ms 40056 KB Time limit exceeded
38 Execution timed out 1085 ms 150264 KB Time limit exceeded
39 Execution timed out 1073 ms 44920 KB Time limit exceeded
40 Execution timed out 1090 ms 79224 KB Time limit exceeded
41 Correct 67 ms 39928 KB Output is correct
42 Execution timed out 1085 ms 211580 KB Time limit exceeded