oj.uz

Submission #155726

# Submission time Handle Problem Language Result Execution time Memory
155726 2019-09-30T06:50:34 Z souhhcong Brunhilda’s Birthday (BOI13_brunhilda) C++14
23.6508 / 100
 1000 ms 212448 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 < p[i])
        {
            dp[x] = 1;
            return dp[x];
        }
        if (x % p[i] == 0) continue;
        mn = min(mn,solve(x-(x%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:31: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:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:41: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 34 ms 39416 KB Output is correct
2 Correct 36 ms 39416 KB Output is correct
3 Correct 34 ms 39548 KB Output is correct
4 Correct 38 ms 39416 KB Output is correct
5 Correct 34 ms 39416 KB Output is correct
6 Correct 34 ms 39416 KB Output is correct
7 Correct 34 ms 39544 KB Output is correct
8 Correct 34 ms 39544 KB Output is correct
9 Correct 34 ms 39420 KB Output is correct
10 Correct 34 ms 39516 KB Output is correct
11 Correct 36 ms 39544 KB Output is correct
12 Correct 34 ms 39416 KB Output is correct
13 Correct 40 ms 39508 KB Output is correct
14 Correct 36 ms 39416 KB Output is correct
15 Correct 35 ms 39468 KB Output is correct
16 Correct 35 ms 39416 KB Output is correct
17 Correct 38 ms 39476 KB Output is correct
18 Correct 39 ms 39468 KB Output is correct

Subtask #2
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 41948 KB Time limit exceeded
2 Correct 54 ms 39892 KB Output is correct
3 Execution timed out 1064 ms 78660 KB Time limit exceeded
4 Execution timed out 1071 ms 60436 KB Time limit exceeded
5 Execution timed out 1072 ms 52088 KB Time limit exceeded
6 Execution timed out 1070 ms 47096 KB Time limit exceeded
7 Execution timed out 1073 ms 41976 KB Time limit exceeded
8 Execution timed out 1065 ms 47608 KB Time limit exceeded
9 Execution timed out 1058 ms 48888 KB Time limit exceeded
10 Execution timed out 1046 ms 78784 KB Time limit exceeded
11 Execution timed out 1063 ms 197944 KB Time limit exceeded
12 Execution timed out 1076 ms 89488 KB Time limit exceeded
13 Execution timed out 1012 ms 60664 KB Time limit exceeded
14 Execution timed out 1056 ms 60408 KB Time limit exceeded
15 Execution timed out 1073 ms 71820 KB Time limit exceeded
16 Correct 55 ms 39804 KB Output is correct
17 Execution timed out 1062 ms 210256 KB Time limit exceeded
18 Execution timed out 1012 ms 97784 KB Time limit exceeded

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 181852 KB Time limit exceeded
2 Execution timed out 1099 ms 175580 KB Time limit exceeded
3 Execution timed out 1090 ms 145240 KB Time limit exceeded
4 Execution timed out 1072 ms 111320 KB Time limit exceeded
5 Execution timed out 1073 ms 40056 KB Time limit exceeded
6 Execution timed out 1079 ms 150264 KB Time limit exceeded
7 Execution timed out 1085 ms 53752 KB Time limit exceeded
8 Execution timed out 1090 ms 182008 KB Time limit exceeded
9 Execution timed out 1102 ms 181880 KB Time limit exceeded
10 Execution timed out 1088 ms 44152 KB Time limit exceeded
11 Execution timed out 1091 ms 68856 KB Time limit exceeded
12 Execution timed out 1094 ms 124664 KB Time limit exceeded
13 Execution timed out 1097 ms 88696 KB Time limit exceeded
14 Execution timed out 1089 ms 143224 KB Time limit exceeded
15 Execution timed out 1098 ms 204024 KB Time limit exceeded
16 Execution timed out 1086 ms 136404 KB Time limit exceeded
17 Execution timed out 1078 ms 46284 KB Time limit exceeded
18 Execution timed out 1090 ms 175736 KB Time limit exceeded
19 Execution timed out 1107 ms 47480 KB Time limit exceeded
20 Execution timed out 1091 ms 145176 KB Time limit exceeded
21 Execution timed out 1101 ms 212448 KB Time limit exceeded
22 Execution timed out 1090 ms 137848 KB Time limit exceeded
23 Execution timed out 1086 ms 40184 KB Time limit exceeded
24 Execution timed out 1087 ms 45176 KB Time limit exceeded
25 Execution timed out 1084 ms 43256 KB Time limit exceeded
26 Execution timed out 1098 ms 111224 KB Time limit exceeded
27 Execution timed out 1102 ms 133624 KB Time limit exceeded
28 Execution timed out 1095 ms 71032 KB Time limit exceeded
29 Execution timed out 1083 ms 69624 KB Time limit exceeded
30 Execution timed out 1080 ms 56908 KB Time limit exceeded
31 Execution timed out 1081 ms 61812 KB Time limit exceeded
32 Execution timed out 1080 ms 64504 KB Time limit exceeded
33 Execution timed out 1062 ms 45308 KB Time limit exceeded
34 Execution timed out 1073 ms 53880 KB Time limit exceeded
35 Execution timed out 1043 ms 49656 KB Time limit exceeded
36 Execution timed out 1076 ms 147960 KB Time limit exceeded
37 Execution timed out 1081 ms 40056 KB Time limit exceeded
38 Execution timed out 1086 ms 150252 KB Time limit exceeded
39 Execution timed out 1087 ms 44920 KB Time limit exceeded
40 Execution timed out 1088 ms 79324 KB Time limit exceeded
41 Correct 67 ms 40000 KB Output is correct
42 Execution timed out 1102 ms 211576 KB Time limit exceeded