oj.uz

Submission #38304

# Submission time Handle Problem Language Result Execution time Memory
38304 2018-01-03T15:01:10 Z Just_Solve_The_Problem Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5836 ms 93448 KB 
#include <bits/stdc++.h>

using namespace std;

#define pii pair < int, int >
#define fr first
#define sc second

const int N = (int)1e5 + 7;
const int m = 1 << 10;

int a[N], k[N];
int bit[m];
pii dp[m][m][11];
int par[N];

main () {
    int n; scanf ("%d", &n);
    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= n; i++)
            if (!j)
                scanf ("%d", a + i);
            else
                scanf ("%d", k + i);

    for (int i = 1; i < m; i++) {
        bit[i] = __builtin_popcount(i);
    }
    int ans, ansid;
    ans = ansid = 0;
    for (int i = 1; i <= n; i++) {
        int pr = (a[i] >> 10);
        int sf = (a[i] % m);
        int mx = 1, id = 0;
        for (int j = 0; j < m; j++) {
            int need = k[i] - bit[j & pr];
            if (need < 0 || need > 10) continue;
            if (mx < dp[j][sf][need].fr + 1) {
                mx = dp[j][sf][need].fr + 1;
                id = dp[j][sf][need].sc;
            }
        }
        par[i] = id;
        for (int j = 0; j < m; j++) {
            int need = bit[j & sf];

            if (dp[pr][j][need].fr < mx) {
                dp[pr][j][need] = {mx, i};
            }
        }
        if (ans < mx) {
            ans = mx;
            ansid = i;
        }
    }
    cout << ans << endl;
    vector < int > asd;
    while (ansid) {
        asd.push_back(ansid);
        ansid = par[ansid];
    }
    reverse(asd.begin(), asd.end());
    for (auto to : asd) {
        cout << to << ' ';
    }
}

Compilation message

subsequence.cpp:17:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:18:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf ("%d", &n);
                            ^
subsequence.cpp:22:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", a + i);
                                    ^
subsequence.cpp:24:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", k + i);
                                    ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 0 ms 93304 KB answer = 3
9 Correct 0 ms 93304 KB answer = 2
10 Correct 3 ms 93304 KB answer = 3
11 Correct 0 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 9 ms 93304 KB answer = 1
16 Correct 3 ms 93304 KB answer = 1
17 Correct 0 ms 93304 KB answer = 1
18 Correct 3 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 3 ms 93304 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 0 ms 93304 KB answer = 3
9 Correct 0 ms 93304 KB answer = 2
10 Correct 3 ms 93304 KB answer = 3
11 Correct 0 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 9 ms 93304 KB answer = 1
16 Correct 3 ms 93304 KB answer = 1
17 Correct 0 ms 93304 KB answer = 1
18 Correct 3 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 3 ms 93304 KB answer = 1
22 Correct 179 ms 93304 KB answer = 358
23 Correct 206 ms 93304 KB answer = 336
24 Correct 203 ms 93304 KB answer = 339
25 Correct 193 ms 93304 KB answer = 357
26 Correct 186 ms 93304 KB answer = 354
27 Correct 213 ms 93304 KB answer = 333
28 Correct 179 ms 93304 KB answer = 314
29 Correct 153 ms 93304 KB answer = 322
30 Correct 189 ms 93304 KB answer = 339
31 Correct 209 ms 93304 KB answer = 351
32 Correct 303 ms 93304 KB answer = 1
33 Correct 276 ms 93304 KB answer = 1
34 Correct 233 ms 93304 KB answer = 1
35 Correct 253 ms 93304 KB answer = 1
36 Correct 259 ms 93304 KB answer = 1
37 Correct 63 ms 93304 KB answer = 1
38 Correct 89 ms 93304 KB answer = 1
39 Correct 66 ms 93304 KB answer = 1
40 Correct 49 ms 93304 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 0 ms 93304 KB answer = 3
9 Correct 0 ms 93304 KB answer = 2
10 Correct 3 ms 93304 KB answer = 3
11 Correct 0 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 9 ms 93304 KB answer = 1
16 Correct 3 ms 93304 KB answer = 1
17 Correct 0 ms 93304 KB answer = 1
18 Correct 3 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 3 ms 93304 KB answer = 1
22 Correct 179 ms 93304 KB answer = 358
23 Correct 206 ms 93304 KB answer = 336
24 Correct 203 ms 93304 KB answer = 339
25 Correct 193 ms 93304 KB answer = 357
26 Correct 186 ms 93304 KB answer = 354
27 Correct 213 ms 93304 KB answer = 333
28 Correct 179 ms 93304 KB answer = 314
29 Correct 153 ms 93304 KB answer = 322
30 Correct 189 ms 93304 KB answer = 339
31 Correct 209 ms 93304 KB answer = 351
32 Correct 303 ms 93304 KB answer = 1
33 Correct 276 ms 93304 KB answer = 1
34 Correct 233 ms 93304 KB answer = 1
35 Correct 253 ms 93304 KB answer = 1
36 Correct 259 ms 93304 KB answer = 1
37 Correct 63 ms 93304 KB answer = 1
38 Correct 89 ms 93304 KB answer = 1
39 Correct 66 ms 93304 KB answer = 1
40 Correct 49 ms 93304 KB answer = 1
41 Correct 983 ms 93448 KB answer = 6296
42 Correct 983 ms 93448 KB answer = 6267
43 Correct 1169 ms 93448 KB answer = 6264
44 Correct 1109 ms 93448 KB answer = 6384
45 Correct 1026 ms 93448 KB answer = 6272
46 Correct 1139 ms 93448 KB answer = 6177
47 Correct 1053 ms 93448 KB answer = 6144
48 Correct 1053 ms 93448 KB answer = 6272
49 Correct 1043 ms 93448 KB answer = 6241
50 Correct 979 ms 93448 KB answer = 6169
51 Correct 389 ms 93304 KB answer = 1
52 Correct 363 ms 93304 KB answer = 1
53 Correct 396 ms 93304 KB answer = 1
54 Correct 383 ms 93304 KB answer = 1
55 Correct 376 ms 93304 KB answer = 1
56 Correct 913 ms 93304 KB answer = 1426
57 Correct 953 ms 93304 KB answer = 1427
58 Correct 1066 ms 93304 KB answer = 1428
59 Correct 803 ms 93304 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93304 KB answer = 4
2 Correct 0 ms 93304 KB answer = 1
3 Correct 0 ms 93304 KB answer = 2
4 Correct 0 ms 93304 KB answer = 1
5 Correct 0 ms 93304 KB answer = 2
6 Correct 0 ms 93304 KB answer = 1
7 Correct 0 ms 93304 KB answer = 1
8 Correct 0 ms 93304 KB answer = 3
9 Correct 0 ms 93304 KB answer = 2
10 Correct 3 ms 93304 KB answer = 3
11 Correct 0 ms 93304 KB answer = 2
12 Correct 0 ms 93304 KB answer = 3
13 Correct 3 ms 93304 KB answer = 2
14 Correct 3 ms 93304 KB answer = 1
15 Correct 9 ms 93304 KB answer = 1
16 Correct 3 ms 93304 KB answer = 1
17 Correct 0 ms 93304 KB answer = 1
18 Correct 3 ms 93304 KB answer = 1
19 Correct 3 ms 93304 KB answer = 1
20 Correct 0 ms 93304 KB answer = 1
21 Correct 3 ms 93304 KB answer = 1
22 Correct 179 ms 93304 KB answer = 358
23 Correct 206 ms 93304 KB answer = 336
24 Correct 203 ms 93304 KB answer = 339
25 Correct 193 ms 93304 KB answer = 357
26 Correct 186 ms 93304 KB answer = 354
27 Correct 213 ms 93304 KB answer = 333
28 Correct 179 ms 93304 KB answer = 314
29 Correct 153 ms 93304 KB answer = 322
30 Correct 189 ms 93304 KB answer = 339
31 Correct 209 ms 93304 KB answer = 351
32 Correct 303 ms 93304 KB answer = 1
33 Correct 276 ms 93304 KB answer = 1
34 Correct 233 ms 93304 KB answer = 1
35 Correct 253 ms 93304 KB answer = 1
36 Correct 259 ms 93304 KB answer = 1
37 Correct 63 ms 93304 KB answer = 1
38 Correct 89 ms 93304 KB answer = 1
39 Correct 66 ms 93304 KB answer = 1
40 Correct 49 ms 93304 KB answer = 1
41 Correct 983 ms 93448 KB answer = 6296
42 Correct 983 ms 93448 KB answer = 6267
43 Correct 1169 ms 93448 KB answer = 6264
44 Correct 1109 ms 93448 KB answer = 6384
45 Correct 1026 ms 93448 KB answer = 6272
46 Correct 1139 ms 93448 KB answer = 6177
47 Correct 1053 ms 93448 KB answer = 6144
48 Correct 1053 ms 93448 KB answer = 6272
49 Correct 1043 ms 93448 KB answer = 6241
50 Correct 979 ms 93448 KB answer = 6169
51 Correct 389 ms 93304 KB answer = 1
52 Correct 363 ms 93304 KB answer = 1
53 Correct 396 ms 93304 KB answer = 1
54 Correct 383 ms 93304 KB answer = 1
55 Correct 376 ms 93304 KB answer = 1
56 Correct 913 ms 93304 KB answer = 1426
57 Correct 953 ms 93304 KB answer = 1427
58 Correct 1066 ms 93304 KB answer = 1428
59 Correct 803 ms 93304 KB answer = 1427
60 Correct 4103 ms 93448 KB answer = 7034
61 Correct 3869 ms 93448 KB answer = 7045
62 Correct 3813 ms 93448 KB answer = 7147
63 Correct 3933 ms 93448 KB answer = 7038
64 Correct 3566 ms 93448 KB answer = 7169
65 Correct 3829 ms 93448 KB answer = 6735
66 Correct 3949 ms 93448 KB answer = 6713
67 Correct 3843 ms 93448 KB answer = 6748
68 Correct 3756 ms 93448 KB answer = 6607
69 Correct 3929 ms 93448 KB answer = 6722
70 Correct 5546 ms 93304 KB answer = 1
71 Correct 5513 ms 93304 KB answer = 1
72 Correct 5836 ms 93304 KB answer = 1
73 Correct 5399 ms 93304 KB answer = 1
74 Correct 5529 ms 93304 KB answer = 1
75 Correct 1833 ms 93304 KB answer = 1
76 Correct 1856 ms 93304 KB answer = 1
77 Correct 1949 ms 93304 KB answer = 1
78 Correct 1699 ms 93304 KB answer = 1
79 Correct 2123 ms 93304 KB answer = 21
80 Correct 2723 ms 93304 KB answer = 7
81 Correct 3343 ms 93304 KB answer = 3
82 Correct 3023 ms 93304 KB answer = 2
83 Correct 2639 ms 93304 KB answer = 1
84 Correct 1796 ms 93304 KB answer = 1
85 Correct 1516 ms 93304 KB answer = 1
86 Correct 2136 ms 93304 KB answer = 11
87 Correct 2616 ms 93304 KB answer = 11
88 Correct 2869 ms 93304 KB answer = 6
89 Correct 2489 ms 93304 KB answer = 4
90 Correct 2543 ms 93304 KB answer = 2
91 Correct 1979 ms 93304 KB answer = 2
92 Correct 1489 ms 93304 KB answer = 2
93 Correct 4193 ms 93448 KB answer = 7211
94 Correct 3743 ms 93448 KB answer = 7032
95 Correct 4113 ms 93448 KB answer = 7092
96 Correct 5073 ms 93448 KB answer = 14167
97 Correct 5106 ms 93448 KB answer = 14159
98 Correct 5086 ms 93448 KB answer = 14125
99 Correct 4856 ms 93448 KB answer = 14121
100 Correct 4446 ms 93448 KB answer = 14010
101 Correct 4669 ms 93448 KB answer = 13976
102 Correct 1743 ms 93304 KB answer = 3
103 Correct 1643 ms 93304 KB answer = 2
104 Correct 2283 ms 93304 KB answer = 3
105 Correct 1776 ms 93304 KB answer = 2
106 Correct 1643 ms 93304 KB answer = 3
107 Correct 1846 ms 93304 KB answer = 4
108 Correct 1609 ms 93304 KB answer = 5
109 Correct 1496 ms 93304 KB answer = 8
110 Correct 1049 ms 93304 KB answer = 22
111 Correct 4329 ms 93448 KB answer = 6760
112 Correct 3933 ms 93448 KB answer = 6788
113 Correct 3659 ms 93448 KB answer = 6632