oj.uz

Submission #155733

# Submission time Handle Problem Language Result Execution time Memory
155733 2019-09-30T07:17:16 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
60.4762 / 100
 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

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
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #2
13.3333333333 / 20.0

# Verdict Execution time Memory 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

Subtask #3
27.1428571429 / 60.0

# Verdict Execution time Memory 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