oj.uz

답안 #962161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962161 2024-04-13T08:11:36 Z Cookie Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 3192 ms 93592 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e5 + 5, mxq = 1e5 + 5, sq = 450, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e18 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;
int n;
int mx[(1 << 10)][(1 << 10)][21], a[mxn + 1], k[mxn + 1], dp[mxn + 1], trace[mxn + 1];
int cnt[(1 << 10)][(1 << 10)];
void solve(){
   cin >> n;
   for(int i = 1; i <= n; i++)cin >> a[i];
   for(int i = 1; i <= n; i++)cin >> k[i];
   for(int i = 0; i < (1 << 10); i++){
       for(int j = 0; j < (1 << 10); j++){
           cnt[i][j] = __builtin_popcount(i & j);
       }
   }
   int ans = 0, node = -1;
   for(int i = 1; i <= n; i++){
       int fir = (a[i] % (1 << 10)), fin = (a[i] >> 10); 
       dp[i] = 1; trace[i] = -1;
       for(int j = 0; j < (1 << 10); j++){
           int need = k[i] - cnt[fir][j];
           if(need < 0)continue;
           int cand = mx[j][fin][need];
           if(dp[cand] + 1 > dp[i]){
               dp[i] = dp[cand] + 1; trace[i] = cand; 
           }
       }
       for(int j = 0; j < (1 << 10); j++){
           int have = cnt[j][fin], curr = mx[fir][j][have];
           if(dp[curr] < dp[i]){
               mx[fir][j][have] = i;
           }
       }
       if(dp[i] > ans){
           ans = dp[i]; node = i;
       }
   }
   vt<int>v;
   while(node != -1){
       v.pb(node); node = trace[node];
   }
   reverse(ALL(v));
   cout << ans << "\n";
   for(auto i: v)cout << i << " ";
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("netw.inp", "r", stdin);
    //freopen("netw.out", "w", stdout)
    int tt; tt = 1;
    while(tt--){
        solve();
 
    }
    return(0);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB answer = 4
2 Correct 5 ms 7004 KB answer = 1
3 Correct 3 ms 6792 KB answer = 2
4 Correct 3 ms 7004 KB answer = 1
5 Correct 3 ms 7004 KB answer = 2
6 Correct 4 ms 7004 KB answer = 1
7 Correct 4 ms 7004 KB answer = 1
8 Correct 4 ms 8024 KB answer = 3
9 Correct 4 ms 8028 KB answer = 2
10 Correct 4 ms 7772 KB answer = 3
11 Correct 4 ms 8036 KB answer = 2
12 Correct 4 ms 8024 KB answer = 3
13 Correct 4 ms 7772 KB answer = 2
14 Correct 4 ms 7768 KB answer = 1
15 Correct 4 ms 8024 KB answer = 1
16 Correct 4 ms 8280 KB answer = 1
17 Correct 4 ms 8028 KB answer = 1
18 Correct 4 ms 7516 KB answer = 1
19 Correct 4 ms 7516 KB answer = 1
20 Correct 4 ms 7516 KB answer = 1
21 Correct 4 ms 7512 KB answer = 1

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB answer = 4
2 Correct 5 ms 7004 KB answer = 1
3 Correct 3 ms 6792 KB answer = 2
4 Correct 3 ms 7004 KB answer = 1
5 Correct 3 ms 7004 KB answer = 2
6 Correct 4 ms 7004 KB answer = 1
7 Correct 4 ms 7004 KB answer = 1
8 Correct 4 ms 8024 KB answer = 3
9 Correct 4 ms 8028 KB answer = 2
10 Correct 4 ms 7772 KB answer = 3
11 Correct 4 ms 8036 KB answer = 2
12 Correct 4 ms 8024 KB answer = 3
13 Correct 4 ms 7772 KB answer = 2
14 Correct 4 ms 7768 KB answer = 1
15 Correct 4 ms 8024 KB answer = 1
16 Correct 4 ms 8280 KB answer = 1
17 Correct 4 ms 8028 KB answer = 1
18 Correct 4 ms 7516 KB answer = 1
19 Correct 4 ms 7516 KB answer = 1
20 Correct 4 ms 7516 KB answer = 1
21 Correct 4 ms 7512 KB answer = 1
22 Correct 185 ms 91604 KB answer = 358
23 Correct 165 ms 91428 KB answer = 336
24 Correct 180 ms 91472 KB answer = 339
25 Correct 187 ms 91728 KB answer = 357
26 Correct 176 ms 91276 KB answer = 354
27 Correct 157 ms 87468 KB answer = 333
28 Correct 163 ms 87124 KB answer = 314
29 Correct 177 ms 86144 KB answer = 322
30 Correct 168 ms 87108 KB answer = 339
31 Correct 170 ms 87888 KB answer = 351
32 Correct 179 ms 87816 KB answer = 1
33 Correct 194 ms 88468 KB answer = 1
34 Correct 157 ms 87248 KB answer = 1
35 Correct 179 ms 88404 KB answer = 1
36 Correct 172 ms 88084 KB answer = 1
37 Correct 88 ms 60360 KB answer = 1
38 Correct 85 ms 60360 KB answer = 1
39 Correct 86 ms 60244 KB answer = 1
40 Correct 85 ms 60248 KB answer = 1

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB answer = 4
2 Correct 5 ms 7004 KB answer = 1
3 Correct 3 ms 6792 KB answer = 2
4 Correct 3 ms 7004 KB answer = 1
5 Correct 3 ms 7004 KB answer = 2
6 Correct 4 ms 7004 KB answer = 1
7 Correct 4 ms 7004 KB answer = 1
8 Correct 4 ms 8024 KB answer = 3
9 Correct 4 ms 8028 KB answer = 2
10 Correct 4 ms 7772 KB answer = 3
11 Correct 4 ms 8036 KB answer = 2
12 Correct 4 ms 8024 KB answer = 3
13 Correct 4 ms 7772 KB answer = 2
14 Correct 4 ms 7768 KB answer = 1
15 Correct 4 ms 8024 KB answer = 1
16 Correct 4 ms 8280 KB answer = 1
17 Correct 4 ms 8028 KB answer = 1
18 Correct 4 ms 7516 KB answer = 1
19 Correct 4 ms 7516 KB answer = 1
20 Correct 4 ms 7516 KB answer = 1
21 Correct 4 ms 7512 KB answer = 1
22 Correct 185 ms 91604 KB answer = 358
23 Correct 165 ms 91428 KB answer = 336
24 Correct 180 ms 91472 KB answer = 339
25 Correct 187 ms 91728 KB answer = 357
26 Correct 176 ms 91276 KB answer = 354
27 Correct 157 ms 87468 KB answer = 333
28 Correct 163 ms 87124 KB answer = 314
29 Correct 177 ms 86144 KB answer = 322
30 Correct 168 ms 87108 KB answer = 339
31 Correct 170 ms 87888 KB answer = 351
32 Correct 179 ms 87816 KB answer = 1
33 Correct 194 ms 88468 KB answer = 1
34 Correct 157 ms 87248 KB answer = 1
35 Correct 179 ms 88404 KB answer = 1
36 Correct 172 ms 88084 KB answer = 1
37 Correct 88 ms 60360 KB answer = 1
38 Correct 85 ms 60360 KB answer = 1
39 Correct 86 ms 60244 KB answer = 1
40 Correct 85 ms 60248 KB answer = 1
41 Correct 989 ms 28380 KB answer = 6296
42 Correct 981 ms 28372 KB answer = 6267
43 Correct 989 ms 28372 KB answer = 6264
44 Correct 1018 ms 28376 KB answer = 6384
45 Correct 1039 ms 28376 KB answer = 6272
46 Correct 870 ms 20492 KB answer = 6177
47 Correct 902 ms 20488 KB answer = 6144
48 Correct 909 ms 20500 KB answer = 6272
49 Correct 881 ms 20492 KB answer = 6241
50 Correct 915 ms 20496 KB answer = 6169
51 Correct 829 ms 13464 KB answer = 1
52 Correct 839 ms 13468 KB answer = 1
53 Correct 841 ms 13400 KB answer = 1
54 Correct 845 ms 13468 KB answer = 1
55 Correct 836 ms 13468 KB answer = 1
56 Correct 884 ms 13368 KB answer = 1426
57 Correct 897 ms 13372 KB answer = 1427
58 Correct 851 ms 13380 KB answer = 1428
59 Correct 887 ms 13368 KB answer = 1427

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB answer = 4
2 Correct 5 ms 7004 KB answer = 1
3 Correct 3 ms 6792 KB answer = 2
4 Correct 3 ms 7004 KB answer = 1
5 Correct 3 ms 7004 KB answer = 2
6 Correct 4 ms 7004 KB answer = 1
7 Correct 4 ms 7004 KB answer = 1
8 Correct 4 ms 8024 KB answer = 3
9 Correct 4 ms 8028 KB answer = 2
10 Correct 4 ms 7772 KB answer = 3
11 Correct 4 ms 8036 KB answer = 2
12 Correct 4 ms 8024 KB answer = 3
13 Correct 4 ms 7772 KB answer = 2
14 Correct 4 ms 7768 KB answer = 1
15 Correct 4 ms 8024 KB answer = 1
16 Correct 4 ms 8280 KB answer = 1
17 Correct 4 ms 8028 KB answer = 1
18 Correct 4 ms 7516 KB answer = 1
19 Correct 4 ms 7516 KB answer = 1
20 Correct 4 ms 7516 KB answer = 1
21 Correct 4 ms 7512 KB answer = 1
22 Correct 185 ms 91604 KB answer = 358
23 Correct 165 ms 91428 KB answer = 336
24 Correct 180 ms 91472 KB answer = 339
25 Correct 187 ms 91728 KB answer = 357
26 Correct 176 ms 91276 KB answer = 354
27 Correct 157 ms 87468 KB answer = 333
28 Correct 163 ms 87124 KB answer = 314
29 Correct 177 ms 86144 KB answer = 322
30 Correct 168 ms 87108 KB answer = 339
31 Correct 170 ms 87888 KB answer = 351
32 Correct 179 ms 87816 KB answer = 1
33 Correct 194 ms 88468 KB answer = 1
34 Correct 157 ms 87248 KB answer = 1
35 Correct 179 ms 88404 KB answer = 1
36 Correct 172 ms 88084 KB answer = 1
37 Correct 88 ms 60360 KB answer = 1
38 Correct 85 ms 60360 KB answer = 1
39 Correct 86 ms 60244 KB answer = 1
40 Correct 85 ms 60248 KB answer = 1
41 Correct 989 ms 28380 KB answer = 6296
42 Correct 981 ms 28372 KB answer = 6267
43 Correct 989 ms 28372 KB answer = 6264
44 Correct 1018 ms 28376 KB answer = 6384
45 Correct 1039 ms 28376 KB answer = 6272
46 Correct 870 ms 20492 KB answer = 6177
47 Correct 902 ms 20488 KB answer = 6144
48 Correct 909 ms 20500 KB answer = 6272
49 Correct 881 ms 20492 KB answer = 6241
50 Correct 915 ms 20496 KB answer = 6169
51 Correct 829 ms 13464 KB answer = 1
52 Correct 839 ms 13468 KB answer = 1
53 Correct 841 ms 13400 KB answer = 1
54 Correct 845 ms 13468 KB answer = 1
55 Correct 836 ms 13468 KB answer = 1
56 Correct 884 ms 13368 KB answer = 1426
57 Correct 897 ms 13372 KB answer = 1427
58 Correct 851 ms 13380 KB answer = 1428
59 Correct 887 ms 13368 KB answer = 1427
60 Correct 3136 ms 93216 KB answer = 7034
61 Correct 3019 ms 93212 KB answer = 7045
62 Correct 2932 ms 93212 KB answer = 7147
63 Correct 2795 ms 93212 KB answer = 7038
64 Correct 3081 ms 93212 KB answer = 7169
65 Correct 2874 ms 93148 KB answer = 6735
66 Correct 3077 ms 93232 KB answer = 6713
67 Correct 3003 ms 93016 KB answer = 6748
68 Correct 2936 ms 93084 KB answer = 6607
69 Correct 3009 ms 93144 KB answer = 6722
70 Correct 3192 ms 93364 KB answer = 1
71 Correct 3049 ms 93180 KB answer = 1
72 Correct 3188 ms 93180 KB answer = 1
73 Correct 3076 ms 93024 KB answer = 1
74 Correct 3181 ms 93176 KB answer = 1
75 Correct 1508 ms 93120 KB answer = 1
76 Correct 1509 ms 93592 KB answer = 1
77 Correct 1499 ms 93116 KB answer = 1
78 Correct 1610 ms 93196 KB answer = 1
79 Correct 1275 ms 39516 KB answer = 21
80 Correct 1408 ms 60700 KB answer = 7
81 Correct 1460 ms 78364 KB answer = 3
82 Correct 1536 ms 88352 KB answer = 2
83 Correct 1595 ms 88468 KB answer = 1
84 Correct 1594 ms 92256 KB answer = 1
85 Correct 1529 ms 93080 KB answer = 1
86 Correct 1294 ms 39596 KB answer = 11
87 Correct 1326 ms 60796 KB answer = 11
88 Correct 1407 ms 78212 KB answer = 6
89 Correct 1482 ms 88380 KB answer = 4
90 Correct 1472 ms 88400 KB answer = 2
91 Correct 1495 ms 92332 KB answer = 2
92 Correct 1537 ms 93260 KB answer = 2
93 Correct 2934 ms 93220 KB answer = 7211
94 Correct 3034 ms 93220 KB answer = 7032
95 Correct 3151 ms 93220 KB answer = 7092
96 Correct 2903 ms 93212 KB answer = 14167
97 Correct 2765 ms 93184 KB answer = 14159
98 Correct 2967 ms 93260 KB answer = 14125
99 Correct 2983 ms 93180 KB answer = 14121
100 Correct 2743 ms 93180 KB answer = 14010
101 Correct 2852 ms 93180 KB answer = 13976
102 Correct 1558 ms 93120 KB answer = 3
103 Correct 1531 ms 92052 KB answer = 2
104 Correct 1455 ms 88472 KB answer = 3
105 Correct 1482 ms 93280 KB answer = 2
106 Correct 1513 ms 92712 KB answer = 3
107 Correct 1516 ms 89304 KB answer = 4
108 Correct 1439 ms 79504 KB answer = 5
109 Correct 1313 ms 62032 KB answer = 8
110 Correct 1202 ms 40876 KB answer = 22
111 Correct 3061 ms 93224 KB answer = 6760
112 Correct 2915 ms 93220 KB answer = 6788
113 Correct 3011 ms 92980 KB answer = 6632