oj.uz

답안 #38276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38276 2018-01-03T11:02:59 Z Talant Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5506 ms 108060 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e6 + 1;
const int M = (int)1024;

int n;
int a[N],b[N],bit[N];
int m = 0;
pair<int,int> dp[1025][1025][11];
int p[N];
int nn;

int main () {
        scanf ("%d", &n);

        for (int i = 1; i <= n; i ++)
                scanf ("%d", &a[i]);

        for (int j = 1; j <= n; j ++)
                scanf ("%d", &b[j]);

        for (int i = 0; i <= M; i ++)
                bit[i] = __builtin_popcount(i);

        for (int i = 1; i <= n; i ++) {
                int pr = (a[i] >> 10),sf = (a[i] % M),mx = 1,id = -1;

                for (int j = 0; j < M; j ++) {
                        int cnt = b[i] - bit[j & pr];

                        if (cnt < 0 || cnt > 10)
                                continue;

                        if (mx < dp[j][sf][cnt].fr + 1)
                                mx = dp[j][sf][cnt].fr + 1,id = dp[j][sf][cnt].sc;
                }
                p[i] = id;

                for (int j = 0; j < M; j ++) {
                        int cnt = bit[j & sf];
                        if (dp[pr][j][cnt].fr < mx)
                                dp[pr][j][cnt] = mk(mx,i);
                }
                if (m < mx)
                        m = mx,nn = i;
        }
        cout << m << endl;

        deque <int> dq;

        while (nn != -1) {
                dq.push_front(nn);
                nn = p[nn];
        }
        for (int i = 0; i < dq.size(); i ++)
                cout << dq[i] << " ";
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < dq.size(); i ++)
                           ^
subsequence.cpp:25:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &n);
                         ^
subsequence.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", &a[i]);
                                    ^
subsequence.cpp:31:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", &b[j]);
                                    ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 107928 KB answer = 4
2 Correct 0 ms 107928 KB answer = 1
3 Correct 0 ms 107928 KB answer = 2
4 Correct 0 ms 107928 KB answer = 1
5 Correct 0 ms 107928 KB answer = 2
6 Correct 0 ms 107928 KB answer = 1
7 Correct 0 ms 107928 KB answer = 1
8 Correct 0 ms 107928 KB answer = 3
9 Correct 3 ms 107928 KB answer = 2
10 Correct 0 ms 107928 KB answer = 3
11 Correct 0 ms 107928 KB answer = 2
12 Correct 3 ms 107928 KB answer = 3
13 Correct 0 ms 107928 KB answer = 2
14 Correct 6 ms 107928 KB answer = 1
15 Correct 0 ms 107928 KB answer = 1
16 Correct 6 ms 107928 KB answer = 1
17 Correct 6 ms 107928 KB answer = 1
18 Correct 3 ms 107928 KB answer = 1
19 Correct 3 ms 107928 KB answer = 1
20 Correct 3 ms 107928 KB answer = 1
21 Correct 0 ms 107928 KB answer = 1

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 107928 KB answer = 4
2 Correct 0 ms 107928 KB answer = 1
3 Correct 0 ms 107928 KB answer = 2
4 Correct 0 ms 107928 KB answer = 1
5 Correct 0 ms 107928 KB answer = 2
6 Correct 0 ms 107928 KB answer = 1
7 Correct 0 ms 107928 KB answer = 1
8 Correct 0 ms 107928 KB answer = 3
9 Correct 3 ms 107928 KB answer = 2
10 Correct 0 ms 107928 KB answer = 3
11 Correct 0 ms 107928 KB answer = 2
12 Correct 3 ms 107928 KB answer = 3
13 Correct 0 ms 107928 KB answer = 2
14 Correct 6 ms 107928 KB answer = 1
15 Correct 0 ms 107928 KB answer = 1
16 Correct 6 ms 107928 KB answer = 1
17 Correct 6 ms 107928 KB answer = 1
18 Correct 3 ms 107928 KB answer = 1
19 Correct 3 ms 107928 KB answer = 1
20 Correct 3 ms 107928 KB answer = 1
21 Correct 0 ms 107928 KB answer = 1
22 Correct 176 ms 107928 KB answer = 358
23 Correct 189 ms 107928 KB answer = 336
24 Correct 159 ms 107928 KB answer = 339
25 Correct 186 ms 107928 KB answer = 357
26 Correct 166 ms 107928 KB answer = 354
27 Correct 189 ms 107928 KB answer = 333
28 Correct 166 ms 107928 KB answer = 314
29 Correct 173 ms 107928 KB answer = 322
30 Correct 183 ms 107928 KB answer = 339
31 Correct 203 ms 107928 KB answer = 351
32 Correct 276 ms 107928 KB answer = 1
33 Correct 253 ms 107928 KB answer = 1
34 Correct 219 ms 107928 KB answer = 1
35 Correct 246 ms 107928 KB answer = 1
36 Correct 209 ms 107928 KB answer = 1
37 Correct 46 ms 107928 KB answer = 1
38 Correct 53 ms 107928 KB answer = 1
39 Correct 56 ms 107928 KB answer = 1
40 Correct 49 ms 107928 KB answer = 1

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 107928 KB answer = 4
2 Correct 0 ms 107928 KB answer = 1
3 Correct 0 ms 107928 KB answer = 2
4 Correct 0 ms 107928 KB answer = 1
5 Correct 0 ms 107928 KB answer = 2
6 Correct 0 ms 107928 KB answer = 1
7 Correct 0 ms 107928 KB answer = 1
8 Correct 0 ms 107928 KB answer = 3
9 Correct 3 ms 107928 KB answer = 2
10 Correct 0 ms 107928 KB answer = 3
11 Correct 0 ms 107928 KB answer = 2
12 Correct 3 ms 107928 KB answer = 3
13 Correct 0 ms 107928 KB answer = 2
14 Correct 6 ms 107928 KB answer = 1
15 Correct 0 ms 107928 KB answer = 1
16 Correct 6 ms 107928 KB answer = 1
17 Correct 6 ms 107928 KB answer = 1
18 Correct 3 ms 107928 KB answer = 1
19 Correct 3 ms 107928 KB answer = 1
20 Correct 3 ms 107928 KB answer = 1
21 Correct 0 ms 107928 KB answer = 1
22 Correct 176 ms 107928 KB answer = 358
23 Correct 189 ms 107928 KB answer = 336
24 Correct 159 ms 107928 KB answer = 339
25 Correct 186 ms 107928 KB answer = 357
26 Correct 166 ms 107928 KB answer = 354
27 Correct 189 ms 107928 KB answer = 333
28 Correct 166 ms 107928 KB answer = 314
29 Correct 173 ms 107928 KB answer = 322
30 Correct 183 ms 107928 KB answer = 339
31 Correct 203 ms 107928 KB answer = 351
32 Correct 276 ms 107928 KB answer = 1
33 Correct 253 ms 107928 KB answer = 1
34 Correct 219 ms 107928 KB answer = 1
35 Correct 246 ms 107928 KB answer = 1
36 Correct 209 ms 107928 KB answer = 1
37 Correct 46 ms 107928 KB answer = 1
38 Correct 53 ms 107928 KB answer = 1
39 Correct 56 ms 107928 KB answer = 1
40 Correct 49 ms 107928 KB answer = 1
41 Correct 959 ms 107928 KB answer = 6296
42 Correct 1053 ms 107928 KB answer = 6267
43 Correct 1012 ms 107928 KB answer = 6264
44 Correct 1059 ms 107928 KB answer = 6384
45 Correct 1002 ms 107928 KB answer = 6272
46 Correct 1049 ms 107928 KB answer = 6177
47 Correct 1063 ms 107928 KB answer = 6144
48 Correct 1018 ms 107928 KB answer = 6272
49 Correct 973 ms 107928 KB answer = 6241
50 Correct 966 ms 107928 KB answer = 6169
51 Correct 353 ms 107928 KB answer = 1
52 Correct 349 ms 107928 KB answer = 1
53 Correct 379 ms 107928 KB answer = 1
54 Correct 396 ms 107928 KB answer = 1
55 Correct 406 ms 107928 KB answer = 1
56 Correct 826 ms 107928 KB answer = 1426
57 Correct 846 ms 107928 KB answer = 1427
58 Correct 969 ms 107928 KB answer = 1428
59 Correct 963 ms 107928 KB answer = 1427

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 107928 KB answer = 4
2 Correct 0 ms 107928 KB answer = 1
3 Correct 0 ms 107928 KB answer = 2
4 Correct 0 ms 107928 KB answer = 1
5 Correct 0 ms 107928 KB answer = 2
6 Correct 0 ms 107928 KB answer = 1
7 Correct 0 ms 107928 KB answer = 1
8 Correct 0 ms 107928 KB answer = 3
9 Correct 3 ms 107928 KB answer = 2
10 Correct 0 ms 107928 KB answer = 3
11 Correct 0 ms 107928 KB answer = 2
12 Correct 3 ms 107928 KB answer = 3
13 Correct 0 ms 107928 KB answer = 2
14 Correct 6 ms 107928 KB answer = 1
15 Correct 0 ms 107928 KB answer = 1
16 Correct 6 ms 107928 KB answer = 1
17 Correct 6 ms 107928 KB answer = 1
18 Correct 3 ms 107928 KB answer = 1
19 Correct 3 ms 107928 KB answer = 1
20 Correct 3 ms 107928 KB answer = 1
21 Correct 0 ms 107928 KB answer = 1
22 Correct 176 ms 107928 KB answer = 358
23 Correct 189 ms 107928 KB answer = 336
24 Correct 159 ms 107928 KB answer = 339
25 Correct 186 ms 107928 KB answer = 357
26 Correct 166 ms 107928 KB answer = 354
27 Correct 189 ms 107928 KB answer = 333
28 Correct 166 ms 107928 KB answer = 314
29 Correct 173 ms 107928 KB answer = 322
30 Correct 183 ms 107928 KB answer = 339
31 Correct 203 ms 107928 KB answer = 351
32 Correct 276 ms 107928 KB answer = 1
33 Correct 253 ms 107928 KB answer = 1
34 Correct 219 ms 107928 KB answer = 1
35 Correct 246 ms 107928 KB answer = 1
36 Correct 209 ms 107928 KB answer = 1
37 Correct 46 ms 107928 KB answer = 1
38 Correct 53 ms 107928 KB answer = 1
39 Correct 56 ms 107928 KB answer = 1
40 Correct 49 ms 107928 KB answer = 1
41 Correct 959 ms 107928 KB answer = 6296
42 Correct 1053 ms 107928 KB answer = 6267
43 Correct 1012 ms 107928 KB answer = 6264
44 Correct 1059 ms 107928 KB answer = 6384
45 Correct 1002 ms 107928 KB answer = 6272
46 Correct 1049 ms 107928 KB answer = 6177
47 Correct 1063 ms 107928 KB answer = 6144
48 Correct 1018 ms 107928 KB answer = 6272
49 Correct 973 ms 107928 KB answer = 6241
50 Correct 966 ms 107928 KB answer = 6169
51 Correct 353 ms 107928 KB answer = 1
52 Correct 349 ms 107928 KB answer = 1
53 Correct 379 ms 107928 KB answer = 1
54 Correct 396 ms 107928 KB answer = 1
55 Correct 406 ms 107928 KB answer = 1
56 Correct 826 ms 107928 KB answer = 1426
57 Correct 846 ms 107928 KB answer = 1427
58 Correct 969 ms 107928 KB answer = 1428
59 Correct 963 ms 107928 KB answer = 1427
60 Correct 3739 ms 107928 KB answer = 7034
61 Correct 3839 ms 107928 KB answer = 7045
62 Correct 3733 ms 107928 KB answer = 7147
63 Correct 3713 ms 107928 KB answer = 7038
64 Correct 3679 ms 107928 KB answer = 7169
65 Correct 3703 ms 107928 KB answer = 6735
66 Correct 3736 ms 107928 KB answer = 6713
67 Correct 3659 ms 107928 KB answer = 6748
68 Correct 3729 ms 107928 KB answer = 6607
69 Correct 3799 ms 107928 KB answer = 6722
70 Correct 5506 ms 107928 KB answer = 1
71 Correct 5499 ms 107928 KB answer = 1
72 Correct 5206 ms 107928 KB answer = 1
73 Correct 5229 ms 107928 KB answer = 1
74 Correct 5393 ms 107928 KB answer = 1
75 Correct 1616 ms 107928 KB answer = 1
76 Correct 1596 ms 107928 KB answer = 1
77 Correct 1729 ms 107928 KB answer = 1
78 Correct 1586 ms 107928 KB answer = 1
79 Correct 1919 ms 107928 KB answer = 21
80 Correct 2396 ms 107928 KB answer = 7
81 Correct 2823 ms 107928 KB answer = 3
82 Correct 2569 ms 107928 KB answer = 2
83 Correct 2233 ms 107928 KB answer = 1
84 Correct 1916 ms 107928 KB answer = 1
85 Correct 1456 ms 107928 KB answer = 1
86 Correct 2069 ms 107928 KB answer = 11
87 Correct 2723 ms 107928 KB answer = 11
88 Correct 3019 ms 107928 KB answer = 6
89 Correct 2833 ms 107928 KB answer = 4
90 Correct 2109 ms 107928 KB answer = 2
91 Correct 1813 ms 107928 KB answer = 2
92 Correct 1723 ms 107928 KB answer = 2
93 Correct 3786 ms 107928 KB answer = 7211
94 Correct 3879 ms 107928 KB answer = 7032
95 Correct 3786 ms 107928 KB answer = 7092
96 Correct 4759 ms 108060 KB answer = 14167
97 Correct 4596 ms 108060 KB answer = 14159
98 Correct 4393 ms 108060 KB answer = 14125
99 Correct 4453 ms 108060 KB answer = 14121
100 Correct 4639 ms 108060 KB answer = 14010
101 Correct 4563 ms 108060 KB answer = 13976
102 Correct 1489 ms 107928 KB answer = 3
103 Correct 1836 ms 107928 KB answer = 2
104 Correct 2179 ms 107928 KB answer = 3
105 Correct 1589 ms 107928 KB answer = 2
106 Correct 1573 ms 107928 KB answer = 3
107 Correct 1783 ms 107928 KB answer = 4
108 Correct 1653 ms 107928 KB answer = 5
109 Correct 1219 ms 107928 KB answer = 8
110 Correct 796 ms 107928 KB answer = 22
111 Correct 3489 ms 107928 KB answer = 6760
112 Correct 3796 ms 107928 KB answer = 6788
113 Correct 3716 ms 107928 KB answer = 6632