oj.uz

Submission #474063

# Submission time Handle Problem Language Result Execution time Memory
474063 2021-09-16T18:29:08 Z ogibogi2004 Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 4655 ms 97184 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int MAXA=(1<<20);
const int MAXHALF=(1<<10);
int n;
int a[MAXN];
int k[MAXN];
int maxlen[MAXHALF][MAXHALF][22];
int cntbits[MAXHALF][MAXHALF];
int dp[MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>k[i];
    for(int i1=0;i1<MAXHALF;++i1)
    {
        for(int i2=0;i2<MAXHALF;++i2)
        {
            cntbits[i1][i2]=__builtin_popcount(i1&i2);
        }
    }
    int maxdp=0;
    for(int i=1;i<=n;++i)
    {
        dp[i]=1;
        int a1=a[i]/MAXHALF,a2=a[i]%MAXHALF;
        for(int j=0;j<MAXHALF;++j)
        {
            int t=cntbits[a1][j];
            if(t>k[i])continue;
            dp[i]=max(dp[i],maxlen[j][a2][k[i]-t]+1);
        }
        for(int j=0;j<MAXHALF;++j)
        {
            maxlen[a1][j][cntbits[j][a2]]=max(maxlen[a1][j][cntbits[j][a2]],dp[i]);
        }
        maxdp=max(maxdp,dp[i]);
    }
    cout<<maxdp<<'\n';
    vector<int>v;
    for(int i=n;i>=1;i--)
    {
        if(dp[i]==maxdp)
        {
            v.push_back(i);
            break;
        }
    }
    for(int i=v.back()-1;i>0;i--)
    {
        if(dp[i]==dp[v.back()]-1&&__builtin_popcount(a[i]&a[v.back()])==k[v.back()])
        {
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    for(auto xd:v)
    {
        cout<<xd<<" ";
    }
    cout<<'\n';
return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB answer = 4
2 Correct 6 ms 4668 KB answer = 1
3 Correct 6 ms 4684 KB answer = 2
4 Correct 5 ms 4684 KB answer = 1
5 Correct 5 ms 4684 KB answer = 2
6 Correct 7 ms 4812 KB answer = 1
7 Correct 5 ms 4684 KB answer = 1
8 Correct 11 ms 5836 KB answer = 3
9 Correct 11 ms 5708 KB answer = 2
10 Correct 11 ms 5708 KB answer = 3
11 Correct 10 ms 5716 KB answer = 2
12 Correct 12 ms 5964 KB answer = 3
13 Correct 10 ms 5708 KB answer = 2
14 Correct 11 ms 5580 KB answer = 1
15 Correct 12 ms 5968 KB answer = 1
16 Correct 12 ms 5968 KB answer = 1
17 Correct 12 ms 5596 KB answer = 1
18 Correct 8 ms 4824 KB answer = 1
19 Correct 8 ms 4812 KB answer = 1
20 Correct 8 ms 4684 KB answer = 1
21 Correct 8 ms 4836 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB answer = 4
2 Correct 6 ms 4668 KB answer = 1
3 Correct 6 ms 4684 KB answer = 2
4 Correct 5 ms 4684 KB answer = 1
5 Correct 5 ms 4684 KB answer = 2
6 Correct 7 ms 4812 KB answer = 1
7 Correct 5 ms 4684 KB answer = 1
8 Correct 11 ms 5836 KB answer = 3
9 Correct 11 ms 5708 KB answer = 2
10 Correct 11 ms 5708 KB answer = 3
11 Correct 10 ms 5716 KB answer = 2
12 Correct 12 ms 5964 KB answer = 3
13 Correct 10 ms 5708 KB answer = 2
14 Correct 11 ms 5580 KB answer = 1
15 Correct 12 ms 5968 KB answer = 1
16 Correct 12 ms 5968 KB answer = 1
17 Correct 12 ms 5596 KB answer = 1
18 Correct 8 ms 4824 KB answer = 1
19 Correct 8 ms 4812 KB answer = 1
20 Correct 8 ms 4684 KB answer = 1
21 Correct 8 ms 4836 KB answer = 1
22 Correct 255 ms 94256 KB answer = 358
23 Correct 257 ms 94328 KB answer = 336
24 Correct 260 ms 94000 KB answer = 339
25 Correct 264 ms 94244 KB answer = 357
26 Correct 251 ms 94148 KB answer = 354
27 Correct 239 ms 88008 KB answer = 333
28 Correct 248 ms 89152 KB answer = 314
29 Correct 237 ms 88476 KB answer = 322
30 Correct 252 ms 89456 KB answer = 339
31 Correct 245 ms 88260 KB answer = 351
32 Correct 257 ms 90004 KB answer = 1
33 Correct 265 ms 89872 KB answer = 1
34 Correct 252 ms 89560 KB answer = 1
35 Correct 262 ms 89916 KB answer = 1
36 Correct 262 ms 89156 KB answer = 1
37 Correct 111 ms 8868 KB answer = 1
38 Correct 111 ms 8900 KB answer = 1
39 Correct 104 ms 8840 KB answer = 1
40 Correct 117 ms 8768 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB answer = 4
2 Correct 6 ms 4668 KB answer = 1
3 Correct 6 ms 4684 KB answer = 2
4 Correct 5 ms 4684 KB answer = 1
5 Correct 5 ms 4684 KB answer = 2
6 Correct 7 ms 4812 KB answer = 1
7 Correct 5 ms 4684 KB answer = 1
8 Correct 11 ms 5836 KB answer = 3
9 Correct 11 ms 5708 KB answer = 2
10 Correct 11 ms 5708 KB answer = 3
11 Correct 10 ms 5716 KB answer = 2
12 Correct 12 ms 5964 KB answer = 3
13 Correct 10 ms 5708 KB answer = 2
14 Correct 11 ms 5580 KB answer = 1
15 Correct 12 ms 5968 KB answer = 1
16 Correct 12 ms 5968 KB answer = 1
17 Correct 12 ms 5596 KB answer = 1
18 Correct 8 ms 4824 KB answer = 1
19 Correct 8 ms 4812 KB answer = 1
20 Correct 8 ms 4684 KB answer = 1
21 Correct 8 ms 4836 KB answer = 1
22 Correct 255 ms 94256 KB answer = 358
23 Correct 257 ms 94328 KB answer = 336
24 Correct 260 ms 94000 KB answer = 339
25 Correct 264 ms 94244 KB answer = 357
26 Correct 251 ms 94148 KB answer = 354
27 Correct 239 ms 88008 KB answer = 333
28 Correct 248 ms 89152 KB answer = 314
29 Correct 237 ms 88476 KB answer = 322
30 Correct 252 ms 89456 KB answer = 339
31 Correct 245 ms 88260 KB answer = 351
32 Correct 257 ms 90004 KB answer = 1
33 Correct 265 ms 89872 KB answer = 1
34 Correct 252 ms 89560 KB answer = 1
35 Correct 262 ms 89916 KB answer = 1
36 Correct 262 ms 89156 KB answer = 1
37 Correct 111 ms 8868 KB answer = 1
38 Correct 111 ms 8900 KB answer = 1
39 Correct 104 ms 8840 KB answer = 1
40 Correct 117 ms 8768 KB answer = 1
41 Correct 1633 ms 6088 KB answer = 6296
42 Correct 1683 ms 5836 KB answer = 6267
43 Correct 1755 ms 5916 KB answer = 6264
44 Correct 1665 ms 5964 KB answer = 6384
45 Correct 1717 ms 6104 KB answer = 6272
46 Correct 1680 ms 5896 KB answer = 6177
47 Correct 1683 ms 6212 KB answer = 6144
48 Correct 1677 ms 6020 KB answer = 6272
49 Correct 1680 ms 6108 KB answer = 6241
50 Correct 1699 ms 6060 KB answer = 6169
51 Correct 1621 ms 5948 KB answer = 1
52 Correct 1751 ms 5952 KB answer = 1
53 Correct 1719 ms 5812 KB answer = 1
54 Correct 1775 ms 5948 KB answer = 1
55 Correct 1687 ms 6048 KB answer = 1
56 Correct 1654 ms 5896 KB answer = 1426
57 Correct 1618 ms 5828 KB answer = 1427
58 Correct 1619 ms 5928 KB answer = 1428
59 Correct 1614 ms 6096 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB answer = 4
2 Correct 6 ms 4668 KB answer = 1
3 Correct 6 ms 4684 KB answer = 2
4 Correct 5 ms 4684 KB answer = 1
5 Correct 5 ms 4684 KB answer = 2
6 Correct 7 ms 4812 KB answer = 1
7 Correct 5 ms 4684 KB answer = 1
8 Correct 11 ms 5836 KB answer = 3
9 Correct 11 ms 5708 KB answer = 2
10 Correct 11 ms 5708 KB answer = 3
11 Correct 10 ms 5716 KB answer = 2
12 Correct 12 ms 5964 KB answer = 3
13 Correct 10 ms 5708 KB answer = 2
14 Correct 11 ms 5580 KB answer = 1
15 Correct 12 ms 5968 KB answer = 1
16 Correct 12 ms 5968 KB answer = 1
17 Correct 12 ms 5596 KB answer = 1
18 Correct 8 ms 4824 KB answer = 1
19 Correct 8 ms 4812 KB answer = 1
20 Correct 8 ms 4684 KB answer = 1
21 Correct 8 ms 4836 KB answer = 1
22 Correct 255 ms 94256 KB answer = 358
23 Correct 257 ms 94328 KB answer = 336
24 Correct 260 ms 94000 KB answer = 339
25 Correct 264 ms 94244 KB answer = 357
26 Correct 251 ms 94148 KB answer = 354
27 Correct 239 ms 88008 KB answer = 333
28 Correct 248 ms 89152 KB answer = 314
29 Correct 237 ms 88476 KB answer = 322
30 Correct 252 ms 89456 KB answer = 339
31 Correct 245 ms 88260 KB answer = 351
32 Correct 257 ms 90004 KB answer = 1
33 Correct 265 ms 89872 KB answer = 1
34 Correct 252 ms 89560 KB answer = 1
35 Correct 262 ms 89916 KB answer = 1
36 Correct 262 ms 89156 KB answer = 1
37 Correct 111 ms 8868 KB answer = 1
38 Correct 111 ms 8900 KB answer = 1
39 Correct 104 ms 8840 KB answer = 1
40 Correct 117 ms 8768 KB answer = 1
41 Correct 1633 ms 6088 KB answer = 6296
42 Correct 1683 ms 5836 KB answer = 6267
43 Correct 1755 ms 5916 KB answer = 6264
44 Correct 1665 ms 5964 KB answer = 6384
45 Correct 1717 ms 6104 KB answer = 6272
46 Correct 1680 ms 5896 KB answer = 6177
47 Correct 1683 ms 6212 KB answer = 6144
48 Correct 1677 ms 6020 KB answer = 6272
49 Correct 1680 ms 6108 KB answer = 6241
50 Correct 1699 ms 6060 KB answer = 6169
51 Correct 1621 ms 5948 KB answer = 1
52 Correct 1751 ms 5952 KB answer = 1
53 Correct 1719 ms 5812 KB answer = 1
54 Correct 1775 ms 5948 KB answer = 1
55 Correct 1687 ms 6048 KB answer = 1
56 Correct 1654 ms 5896 KB answer = 1426
57 Correct 1618 ms 5828 KB answer = 1427
58 Correct 1619 ms 5928 KB answer = 1428
59 Correct 1614 ms 6096 KB answer = 1427
60 Correct 4136 ms 96144 KB answer = 7034
61 Correct 4235 ms 97052 KB answer = 7045
62 Correct 4331 ms 96992 KB answer = 7147
63 Correct 4310 ms 97056 KB answer = 7038
64 Correct 4418 ms 97184 KB answer = 7169
65 Correct 4180 ms 96868 KB answer = 6735
66 Correct 4145 ms 96556 KB answer = 6713
67 Correct 4196 ms 96772 KB answer = 6748
68 Correct 4167 ms 96612 KB answer = 6607
69 Correct 4258 ms 96716 KB answer = 6722
70 Correct 4655 ms 96856 KB answer = 1
71 Correct 4569 ms 97124 KB answer = 1
72 Correct 4383 ms 96968 KB answer = 1
73 Correct 4466 ms 96756 KB answer = 1
74 Correct 4360 ms 96916 KB answer = 1
75 Correct 2456 ms 55844 KB answer = 1
76 Correct 2387 ms 56140 KB answer = 1
77 Correct 2274 ms 55908 KB answer = 1
78 Correct 2301 ms 55916 KB answer = 1
79 Correct 2617 ms 41088 KB answer = 21
80 Correct 3092 ms 63404 KB answer = 7
81 Correct 3203 ms 81840 KB answer = 3
82 Correct 3016 ms 92196 KB answer = 2
83 Correct 2743 ms 83908 KB answer = 1
84 Correct 2466 ms 65932 KB answer = 1
85 Correct 2358 ms 56124 KB answer = 1
86 Correct 2598 ms 41336 KB answer = 11
87 Correct 3164 ms 63300 KB answer = 11
88 Correct 3043 ms 81748 KB answer = 6
89 Correct 3103 ms 92116 KB answer = 4
90 Correct 2797 ms 84004 KB answer = 2
91 Correct 2574 ms 65844 KB answer = 2
92 Correct 2570 ms 55960 KB answer = 2
93 Correct 4319 ms 96900 KB answer = 7211
94 Correct 4417 ms 96820 KB answer = 7032
95 Correct 4350 ms 96796 KB answer = 7092
96 Correct 3984 ms 96844 KB answer = 14167
97 Correct 4074 ms 96912 KB answer = 14159
98 Correct 4093 ms 96924 KB answer = 14125
99 Correct 4011 ms 96956 KB answer = 14121
100 Correct 4006 ms 97036 KB answer = 14010
101 Correct 3996 ms 96884 KB answer = 13976
102 Correct 2435 ms 55984 KB answer = 3
103 Correct 2594 ms 65688 KB answer = 2
104 Correct 2827 ms 83840 KB answer = 3
105 Correct 2453 ms 55192 KB answer = 2
106 Correct 2513 ms 65628 KB answer = 3
107 Correct 2762 ms 92040 KB answer = 4
108 Correct 2967 ms 81712 KB answer = 5
109 Correct 2999 ms 63328 KB answer = 8
110 Correct 2568 ms 41196 KB answer = 22
111 Correct 4155 ms 96820 KB answer = 6760
112 Correct 4211 ms 96612 KB answer = 6788
113 Correct 4289 ms 96668 KB answer = 6632