oj.uz

답안 #36962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36962 2017-12-19T16:33:51 Z nickyrio Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 4973 ms 48784 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define N 100100
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "TEST"
using namespace std;

int n, a[N], k[N], cnt[1024], dp[1024][1024][11], f[N], bef[N];
vector<int> res;
int main() {
    //freopen(taskname".inp","r",stdin);
    //freopen(taskname".out","w",stdout);
    IO;
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n) scanf("%d", &k[i]);
    REP(i, 1 << 10) cnt[i] = __builtin_popcount(i);
    //
    f[0] = 0;int ans = 0;
    FOR(i, 1, n) {
        int A = a[i] / 1024, B = a[i] % 1024;
        int best = 0;
        REP(newB, 1024) {
            int C = k[i] - cnt[B & newB];
            if (C > 10 || C < 0) continue;
            if (f[best] < f[dp[A][newB][C]]) best = dp[A][newB][C];
        } 
        f[i] = f[best] + 1;
        bef[i] = best;
        if (f[i] > f[ans]) ans = i;
        //
        REP(newA, 1024) {
            int C = cnt[A & newA];
            if (f[dp[newA][B][C]] < f[i]) {
                dp[newA][B][C] = i;
            }
        }
    }
    printf("%d\n", f[ans]);
    while (ans > 0) {
        res.push_back(ans);
        ans = bef[ans];
    }
    while (!res.empty()) printf("%d ", res.back()), res.pop_back();
}

Compilation message

subsequence.cpp: In function 'int main()':
subsequence.cpp:18:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
subsequence.cpp:20:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &k[i]);
                                    ^

Subtask #1
7.0 / 7.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48640 KB answer = 4
2 Correct 0 ms 48640 KB answer = 1
3 Correct 3 ms 48640 KB answer = 2
4 Correct 0 ms 48640 KB answer = 1
5 Correct 0 ms 48640 KB answer = 2
6 Correct 0 ms 48640 KB answer = 1
7 Correct 0 ms 48640 KB answer = 1
8 Correct 9 ms 48640 KB answer = 3
9 Correct 3 ms 48640 KB answer = 2
10 Correct 3 ms 48640 KB answer = 3
11 Correct 0 ms 48640 KB answer = 2
12 Correct 3 ms 48640 KB answer = 3
13 Correct 9 ms 48640 KB answer = 2
14 Correct 0 ms 48640 KB answer = 1
15 Correct 3 ms 48640 KB answer = 1
16 Correct 0 ms 48640 KB answer = 1
17 Correct 3 ms 48640 KB answer = 1
18 Correct 0 ms 48640 KB answer = 1
19 Correct 0 ms 48640 KB answer = 1
20 Correct 6 ms 48640 KB answer = 1
21 Correct 0 ms 48640 KB answer = 1
22 Correct 196 ms 48640 KB answer = 358
23 Correct 243 ms 48640 KB answer = 336
24 Correct 243 ms 48640 KB answer = 339
25 Correct 233 ms 48640 KB answer = 357
26 Correct 259 ms 48640 KB answer = 354
27 Correct 216 ms 48640 KB answer = 333
28 Correct 226 ms 48640 KB answer = 314
29 Correct 246 ms 48640 KB answer = 322
30 Correct 253 ms 48640 KB answer = 339
31 Correct 219 ms 48640 KB answer = 351
32 Correct 219 ms 48640 KB answer = 1
33 Correct 223 ms 48640 KB answer = 1
34 Correct 219 ms 48640 KB answer = 1
35 Correct 233 ms 48640 KB answer = 1
36 Correct 216 ms 48640 KB answer = 1
37 Correct 149 ms 48640 KB answer = 1
38 Correct 189 ms 48640 KB answer = 1
39 Correct 163 ms 48640 KB answer = 1
40 Correct 153 ms 48640 KB answer = 1

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48640 KB answer = 4
2 Correct 0 ms 48640 KB answer = 1
3 Correct 3 ms 48640 KB answer = 2
4 Correct 0 ms 48640 KB answer = 1
5 Correct 0 ms 48640 KB answer = 2
6 Correct 0 ms 48640 KB answer = 1
7 Correct 0 ms 48640 KB answer = 1
8 Correct 9 ms 48640 KB answer = 3
9 Correct 3 ms 48640 KB answer = 2
10 Correct 3 ms 48640 KB answer = 3
11 Correct 0 ms 48640 KB answer = 2
12 Correct 3 ms 48640 KB answer = 3
13 Correct 9 ms 48640 KB answer = 2
14 Correct 0 ms 48640 KB answer = 1
15 Correct 3 ms 48640 KB answer = 1
16 Correct 0 ms 48640 KB answer = 1
17 Correct 3 ms 48640 KB answer = 1
18 Correct 0 ms 48640 KB answer = 1
19 Correct 0 ms 48640 KB answer = 1
20 Correct 6 ms 48640 KB answer = 1
21 Correct 0 ms 48640 KB answer = 1
22 Correct 196 ms 48640 KB answer = 358
23 Correct 243 ms 48640 KB answer = 336
24 Correct 243 ms 48640 KB answer = 339
25 Correct 233 ms 48640 KB answer = 357
26 Correct 259 ms 48640 KB answer = 354
27 Correct 216 ms 48640 KB answer = 333
28 Correct 226 ms 48640 KB answer = 314
29 Correct 246 ms 48640 KB answer = 322
30 Correct 253 ms 48640 KB answer = 339
31 Correct 219 ms 48640 KB answer = 351
32 Correct 219 ms 48640 KB answer = 1
33 Correct 223 ms 48640 KB answer = 1
34 Correct 219 ms 48640 KB answer = 1
35 Correct 233 ms 48640 KB answer = 1
36 Correct 216 ms 48640 KB answer = 1
37 Correct 149 ms 48640 KB answer = 1
38 Correct 189 ms 48640 KB answer = 1
39 Correct 163 ms 48640 KB answer = 1
40 Correct 153 ms 48640 KB answer = 1
41 Correct 2733 ms 48784 KB answer = 6296
42 Correct 2806 ms 48784 KB answer = 6267
43 Correct 2606 ms 48784 KB answer = 6264
44 Correct 2289 ms 48784 KB answer = 6384
45 Correct 2763 ms 48784 KB answer = 6272
46 Correct 1933 ms 48784 KB answer = 6177
47 Correct 1813 ms 48784 KB answer = 6144
48 Correct 1739 ms 48784 KB answer = 6272
49 Correct 1856 ms 48784 KB answer = 6241
50 Correct 1983 ms 48784 KB answer = 6169
51 Correct 1399 ms 48640 KB answer = 1
52 Correct 1603 ms 48640 KB answer = 1
53 Correct 1313 ms 48640 KB answer = 1
54 Correct 1223 ms 48640 KB answer = 1
55 Correct 1476 ms 48640 KB answer = 1
56 Correct 1939 ms 48640 KB answer = 1426
57 Correct 2363 ms 48640 KB answer = 1427
58 Correct 2119 ms 48640 KB answer = 1428
59 Correct 2109 ms 48640 KB answer = 1427

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 48640 KB answer = 4
2 Correct 0 ms 48640 KB answer = 1
3 Correct 3 ms 48640 KB answer = 2
4 Correct 0 ms 48640 KB answer = 1
5 Correct 0 ms 48640 KB answer = 2
6 Correct 0 ms 48640 KB answer = 1
7 Correct 0 ms 48640 KB answer = 1
8 Correct 9 ms 48640 KB answer = 3
9 Correct 3 ms 48640 KB answer = 2
10 Correct 3 ms 48640 KB answer = 3
11 Correct 0 ms 48640 KB answer = 2
12 Correct 3 ms 48640 KB answer = 3
13 Correct 9 ms 48640 KB answer = 2
14 Correct 0 ms 48640 KB answer = 1
15 Correct 3 ms 48640 KB answer = 1
16 Correct 0 ms 48640 KB answer = 1
17 Correct 3 ms 48640 KB answer = 1
18 Correct 0 ms 48640 KB answer = 1
19 Correct 0 ms 48640 KB answer = 1
20 Correct 6 ms 48640 KB answer = 1
21 Correct 0 ms 48640 KB answer = 1
22 Correct 196 ms 48640 KB answer = 358
23 Correct 243 ms 48640 KB answer = 336
24 Correct 243 ms 48640 KB answer = 339
25 Correct 233 ms 48640 KB answer = 357
26 Correct 259 ms 48640 KB answer = 354
27 Correct 216 ms 48640 KB answer = 333
28 Correct 226 ms 48640 KB answer = 314
29 Correct 246 ms 48640 KB answer = 322
30 Correct 253 ms 48640 KB answer = 339
31 Correct 219 ms 48640 KB answer = 351
32 Correct 219 ms 48640 KB answer = 1
33 Correct 223 ms 48640 KB answer = 1
34 Correct 219 ms 48640 KB answer = 1
35 Correct 233 ms 48640 KB answer = 1
36 Correct 216 ms 48640 KB answer = 1
37 Correct 149 ms 48640 KB answer = 1
38 Correct 189 ms 48640 KB answer = 1
39 Correct 163 ms 48640 KB answer = 1
40 Correct 153 ms 48640 KB answer = 1
41 Correct 2733 ms 48784 KB answer = 6296
42 Correct 2806 ms 48784 KB answer = 6267
43 Correct 2606 ms 48784 KB answer = 6264
44 Correct 2289 ms 48784 KB answer = 6384
45 Correct 2763 ms 48784 KB answer = 6272
46 Correct 1933 ms 48784 KB answer = 6177
47 Correct 1813 ms 48784 KB answer = 6144
48 Correct 1739 ms 48784 KB answer = 6272
49 Correct 1856 ms 48784 KB answer = 6241
50 Correct 1983 ms 48784 KB answer = 6169
51 Correct 1399 ms 48640 KB answer = 1
52 Correct 1603 ms 48640 KB answer = 1
53 Correct 1313 ms 48640 KB answer = 1
54 Correct 1223 ms 48640 KB answer = 1
55 Correct 1476 ms 48640 KB answer = 1
56 Correct 1939 ms 48640 KB answer = 1426
57 Correct 2363 ms 48640 KB answer = 1427
58 Correct 2119 ms 48640 KB answer = 1428
59 Correct 2109 ms 48640 KB answer = 1427
60 Correct 3963 ms 48784 KB answer = 7034
61 Correct 4038 ms 48784 KB answer = 7045
62 Correct 3993 ms 48784 KB answer = 7147
63 Correct 4276 ms 48784 KB answer = 7038
64 Correct 4569 ms 48784 KB answer = 7169
65 Correct 4359 ms 48784 KB answer = 6735
66 Correct 4373 ms 48784 KB answer = 6713
67 Correct 4343 ms 48784 KB answer = 6748
68 Correct 4203 ms 48784 KB answer = 6607
69 Correct 4273 ms 48784 KB answer = 6722
70 Correct 4183 ms 48640 KB answer = 1
71 Correct 4199 ms 48640 KB answer = 1
72 Correct 4069 ms 48640 KB answer = 1
73 Correct 4173 ms 48640 KB answer = 1
74 Correct 4319 ms 48640 KB answer = 1
75 Correct 3049 ms 48640 KB answer = 1
76 Correct 3203 ms 48640 KB answer = 1
77 Correct 3023 ms 48640 KB answer = 1
78 Correct 3149 ms 48640 KB answer = 1
79 Correct 2256 ms 48640 KB answer = 21
80 Correct 2783 ms 48640 KB answer = 7
81 Correct 2986 ms 48640 KB answer = 3
82 Correct 2923 ms 48640 KB answer = 2
83 Correct 3019 ms 48640 KB answer = 1
84 Correct 2876 ms 48640 KB answer = 1
85 Correct 2639 ms 48640 KB answer = 1
86 Correct 1903 ms 48640 KB answer = 11
87 Correct 2473 ms 48640 KB answer = 11
88 Correct 2206 ms 48640 KB answer = 6
89 Correct 2636 ms 48640 KB answer = 4
90 Correct 2793 ms 48640 KB answer = 2
91 Correct 2826 ms 48640 KB answer = 2
92 Correct 3183 ms 48640 KB answer = 2
93 Correct 4009 ms 48784 KB answer = 7211
94 Correct 4283 ms 48784 KB answer = 7032
95 Correct 3983 ms 48784 KB answer = 7092
96 Correct 4973 ms 48784 KB answer = 14167
97 Correct 4773 ms 48784 KB answer = 14159
98 Correct 4906 ms 48784 KB answer = 14125
99 Correct 4929 ms 48784 KB answer = 14121
100 Correct 4773 ms 48784 KB answer = 14010
101 Correct 4966 ms 48784 KB answer = 13976
102 Correct 3369 ms 48640 KB answer = 3
103 Correct 3083 ms 48640 KB answer = 2
104 Correct 2993 ms 48640 KB answer = 3
105 Correct 3159 ms 48640 KB answer = 2
106 Correct 2946 ms 48640 KB answer = 3
107 Correct 2806 ms 48640 KB answer = 4
108 Correct 2906 ms 48640 KB answer = 5
109 Correct 2573 ms 48640 KB answer = 8
110 Correct 2353 ms 48640 KB answer = 22
111 Correct 3946 ms 48784 KB answer = 6760
112 Correct 4516 ms 48784 KB answer = 6788
113 Correct 4266 ms 48784 KB answer = 6632