oj.uz

Submission #155756

# Submission time Handle Problem Language Result Execution time Memory
155756 2019-09-30T09:12:45 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 517 ms 118392 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;

const int N = 1e7 + 5;

int dp[N], p[N];

int m, q, last, f[N];

int main() {
    scanf("%d%d", &m, &q);
    for(int i = 0; i < N; i++)
        p[i] = 0;
    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++) {
        if(i > last)
            break;
        if(i)
            f[i] += f[i - 1];
        dp[i] = f[i];
        if(i + p[i] - 1 >= last) {
            f[last + 1] += (dp[i] + 1);
            f[i + p[i]] -= (dp[i] + 1);
            last = max(last, i + p[i] - 1);
        }
    }
    for(int i = 1; i <= q; i++) {
        int x;
        scanf("%d", &x);
        if(dp[x] == 0)
            printf("oo\n");
        else
            printf("%d\n", dp[x]);
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:23: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:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
brunhilda.cpp:48: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 54 ms 39548 KB Output is correct
2 Correct 162 ms 117724 KB Output is correct
3 Correct 68 ms 41468 KB Output is correct
4 Correct 138 ms 117780 KB Output is correct
5 Correct 147 ms 117752 KB Output is correct
6 Correct 53 ms 39544 KB Output is correct
7 Correct 68 ms 41588 KB Output is correct
8 Correct 79 ms 46592 KB Output is correct
9 Correct 173 ms 117724 KB Output is correct
10 Correct 197 ms 117744 KB Output is correct
11 Correct 180 ms 117880 KB Output is correct
12 Correct 133 ms 117672 KB Output is correct
13 Correct 324 ms 117732 KB Output is correct
14 Correct 306 ms 117880 KB Output is correct
15 Correct 174 ms 117752 KB Output is correct
16 Correct 161 ms 117756 KB Output is correct
17 Correct 183 ms 117760 KB Output is correct
18 Correct 159 ms 117752 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 117752 KB Output is correct
2 Correct 196 ms 117808 KB Output is correct
3 Correct 369 ms 117880 KB Output is correct
4 Correct 183 ms 117752 KB Output is correct
5 Correct 267 ms 117728 KB Output is correct
6 Correct 170 ms 117708 KB Output is correct
7 Correct 154 ms 117796 KB Output is correct
8 Correct 182 ms 117752 KB Output is correct
9 Correct 296 ms 117756 KB Output is correct
10 Correct 380 ms 117752 KB Output is correct
11 Correct 363 ms 117720 KB Output is correct
12 Correct 220 ms 117752 KB Output is correct
13 Correct 153 ms 117756 KB Output is correct
14 Correct 182 ms 117748 KB Output is correct
15 Correct 326 ms 117752 KB Output is correct
16 Correct 192 ms 117748 KB Output is correct
17 Correct 384 ms 117728 KB Output is correct
18 Correct 323 ms 117740 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 117804 KB Output is correct
2 Correct 404 ms 117760 KB Output is correct
3 Correct 441 ms 117844 KB Output is correct
4 Correct 259 ms 118008 KB Output is correct
5 Correct 254 ms 118012 KB Output is correct
6 Correct 339 ms 118008 KB Output is correct
7 Correct 359 ms 117848 KB Output is correct
8 Correct 326 ms 117844 KB Output is correct
9 Correct 325 ms 117980 KB Output is correct
10 Correct 296 ms 117720 KB Output is correct
11 Correct 252 ms 117868 KB Output is correct
12 Correct 297 ms 117752 KB Output is correct
13 Correct 385 ms 118012 KB Output is correct
14 Correct 236 ms 118312 KB Output is correct
15 Correct 318 ms 117880 KB Output is correct
16 Correct 341 ms 117880 KB Output is correct
17 Correct 301 ms 117948 KB Output is correct
18 Correct 377 ms 117804 KB Output is correct
19 Correct 163 ms 117780 KB Output is correct
20 Correct 386 ms 117972 KB Output is correct
21 Correct 268 ms 118392 KB Output is correct
22 Correct 405 ms 117976 KB Output is correct
23 Correct 213 ms 117972 KB Output is correct
24 Correct 196 ms 117956 KB Output is correct
25 Correct 282 ms 118008 KB Output is correct
26 Correct 262 ms 118008 KB Output is correct
27 Correct 517 ms 117880 KB Output is correct
28 Correct 194 ms 118156 KB Output is correct
29 Correct 392 ms 118008 KB Output is correct
30 Correct 358 ms 118008 KB Output is correct
31 Correct 215 ms 118112 KB Output is correct
32 Correct 225 ms 118008 KB Output is correct
33 Correct 214 ms 118136 KB Output is correct
34 Correct 350 ms 117880 KB Output is correct
35 Correct 199 ms 118024 KB Output is correct
36 Correct 400 ms 118008 KB Output is correct
37 Correct 221 ms 117884 KB Output is correct
38 Correct 365 ms 118008 KB Output is correct
39 Correct 204 ms 118136 KB Output is correct
40 Correct 282 ms 118008 KB Output is correct
41 Correct 270 ms 117864 KB Output is correct
42 Correct 359 ms 118136 KB Output is correct