oj.uz

Submission #474057

# Submission time Handle Problem Language Result Execution time Memory
474057 2021-09-16T18:23:16 Z ogibogi2004 Longest beautiful sequence (IZhO17_subsequence) C++14
40 / 100
 6000 ms 186456 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];
pair<int,int> maxlen[MAXHALF][MAXHALF][22];
int cntbits[MAXHALF][MAXHALF];
pair<int,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);
        }
    }
    pair<int,int> maxdp;
    maxdp={0,0};
    for(int i=1;i<=n;++i)
    {
        dp[i]={1,0};
        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].first+1,maxlen[j][a2][k[i]-t].second});
        }
        for(int j=0;j<MAXHALF;++j)
        {
            maxlen[a1][j][cntbits[j][a2]]=max(maxlen[a1][j][cntbits[j][a2]],{dp[i].first,i});
        }
        maxdp=max(maxdp,{dp[i].first,i});
    }
    cout<<maxdp.first<<'\n';
    vector<int>v;
    v.push_back(maxdp.second);
    while(dp[v.back()].second!=0)
    {
        v.push_back(dp[v.back()].second);
    }
    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 4852 KB answer = 4
2 Correct 5 ms 4940 KB answer = 1
3 Correct 6 ms 4940 KB answer = 2
4 Correct 6 ms 4940 KB answer = 1
5 Correct 6 ms 4940 KB answer = 2
6 Correct 7 ms 5304 KB answer = 1
7 Correct 6 ms 4940 KB answer = 1
8 Correct 13 ms 7236 KB answer = 3
9 Correct 13 ms 7116 KB answer = 2
10 Correct 14 ms 7072 KB answer = 3
11 Correct 11 ms 7020 KB answer = 2
12 Correct 13 ms 7552 KB answer = 3
13 Correct 12 ms 6916 KB answer = 2
14 Correct 12 ms 6660 KB answer = 1
15 Correct 13 ms 7372 KB answer = 1
16 Correct 15 ms 7452 KB answer = 1
17 Correct 13 ms 6928 KB answer = 1
18 Correct 9 ms 5260 KB answer = 1
19 Correct 10 ms 5300 KB answer = 1
20 Correct 9 ms 5068 KB answer = 1
21 Correct 9 ms 5244 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4852 KB answer = 4
2 Correct 5 ms 4940 KB answer = 1
3 Correct 6 ms 4940 KB answer = 2
4 Correct 6 ms 4940 KB answer = 1
5 Correct 6 ms 4940 KB answer = 2
6 Correct 7 ms 5304 KB answer = 1
7 Correct 6 ms 4940 KB answer = 1
8 Correct 13 ms 7236 KB answer = 3
9 Correct 13 ms 7116 KB answer = 2
10 Correct 14 ms 7072 KB answer = 3
11 Correct 11 ms 7020 KB answer = 2
12 Correct 13 ms 7552 KB answer = 3
13 Correct 12 ms 6916 KB answer = 2
14 Correct 12 ms 6660 KB answer = 1
15 Correct 13 ms 7372 KB answer = 1
16 Correct 15 ms 7452 KB answer = 1
17 Correct 13 ms 6928 KB answer = 1
18 Correct 9 ms 5260 KB answer = 1
19 Correct 10 ms 5300 KB answer = 1
20 Correct 9 ms 5068 KB answer = 1
21 Correct 9 ms 5244 KB answer = 1
22 Correct 417 ms 183896 KB answer = 358
23 Correct 399 ms 184016 KB answer = 336
24 Correct 406 ms 183500 KB answer = 339
25 Correct 404 ms 184096 KB answer = 357
26 Correct 406 ms 184040 KB answer = 354
27 Correct 391 ms 171536 KB answer = 333
28 Correct 411 ms 173804 KB answer = 314
29 Correct 392 ms 172360 KB answer = 322
30 Correct 397 ms 174532 KB answer = 339
31 Correct 392 ms 171900 KB answer = 351
32 Correct 415 ms 175296 KB answer = 1
33 Correct 434 ms 175172 KB answer = 1
34 Correct 417 ms 174628 KB answer = 1
35 Correct 420 ms 175296 KB answer = 1
36 Correct 413 ms 173740 KB answer = 1
37 Correct 147 ms 13204 KB answer = 1
38 Correct 149 ms 13268 KB answer = 1
39 Correct 145 ms 13232 KB answer = 1
40 Correct 142 ms 13252 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4852 KB answer = 4
2 Correct 5 ms 4940 KB answer = 1
3 Correct 6 ms 4940 KB answer = 2
4 Correct 6 ms 4940 KB answer = 1
5 Correct 6 ms 4940 KB answer = 2
6 Correct 7 ms 5304 KB answer = 1
7 Correct 6 ms 4940 KB answer = 1
8 Correct 13 ms 7236 KB answer = 3
9 Correct 13 ms 7116 KB answer = 2
10 Correct 14 ms 7072 KB answer = 3
11 Correct 11 ms 7020 KB answer = 2
12 Correct 13 ms 7552 KB answer = 3
13 Correct 12 ms 6916 KB answer = 2
14 Correct 12 ms 6660 KB answer = 1
15 Correct 13 ms 7372 KB answer = 1
16 Correct 15 ms 7452 KB answer = 1
17 Correct 13 ms 6928 KB answer = 1
18 Correct 9 ms 5260 KB answer = 1
19 Correct 10 ms 5300 KB answer = 1
20 Correct 9 ms 5068 KB answer = 1
21 Correct 9 ms 5244 KB answer = 1
22 Correct 417 ms 183896 KB answer = 358
23 Correct 399 ms 184016 KB answer = 336
24 Correct 406 ms 183500 KB answer = 339
25 Correct 404 ms 184096 KB answer = 357
26 Correct 406 ms 184040 KB answer = 354
27 Correct 391 ms 171536 KB answer = 333
28 Correct 411 ms 173804 KB answer = 314
29 Correct 392 ms 172360 KB answer = 322
30 Correct 397 ms 174532 KB answer = 339
31 Correct 392 ms 171900 KB answer = 351
32 Correct 415 ms 175296 KB answer = 1
33 Correct 434 ms 175172 KB answer = 1
34 Correct 417 ms 174628 KB answer = 1
35 Correct 420 ms 175296 KB answer = 1
36 Correct 413 ms 173740 KB answer = 1
37 Correct 147 ms 13204 KB answer = 1
38 Correct 149 ms 13268 KB answer = 1
39 Correct 145 ms 13232 KB answer = 1
40 Correct 142 ms 13252 KB answer = 1
41 Correct 2110 ms 6492 KB answer = 6296
42 Correct 2127 ms 6484 KB answer = 6267
43 Correct 2011 ms 6636 KB answer = 6264
44 Correct 2053 ms 6604 KB answer = 6384
45 Correct 2093 ms 6752 KB answer = 6272
46 Correct 1994 ms 6640 KB answer = 6177
47 Correct 1991 ms 6700 KB answer = 6144
48 Correct 2073 ms 6784 KB answer = 6272
49 Correct 2007 ms 6836 KB answer = 6241
50 Correct 1970 ms 6608 KB answer = 6169
51 Correct 2091 ms 6460 KB answer = 1
52 Correct 2213 ms 6452 KB answer = 1
53 Correct 2156 ms 6656 KB answer = 1
54 Correct 2079 ms 6468 KB answer = 1
55 Correct 2104 ms 6580 KB answer = 1
56 Correct 2111 ms 6520 KB answer = 1426
57 Correct 2058 ms 6468 KB answer = 1427
58 Correct 2097 ms 6556 KB answer = 1428
59 Correct 2051 ms 6488 KB answer = 1427

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4852 KB answer = 4
2 Correct 5 ms 4940 KB answer = 1
3 Correct 6 ms 4940 KB answer = 2
4 Correct 6 ms 4940 KB answer = 1
5 Correct 6 ms 4940 KB answer = 2
6 Correct 7 ms 5304 KB answer = 1
7 Correct 6 ms 4940 KB answer = 1
8 Correct 13 ms 7236 KB answer = 3
9 Correct 13 ms 7116 KB answer = 2
10 Correct 14 ms 7072 KB answer = 3
11 Correct 11 ms 7020 KB answer = 2
12 Correct 13 ms 7552 KB answer = 3
13 Correct 12 ms 6916 KB answer = 2
14 Correct 12 ms 6660 KB answer = 1
15 Correct 13 ms 7372 KB answer = 1
16 Correct 15 ms 7452 KB answer = 1
17 Correct 13 ms 6928 KB answer = 1
18 Correct 9 ms 5260 KB answer = 1
19 Correct 10 ms 5300 KB answer = 1
20 Correct 9 ms 5068 KB answer = 1
21 Correct 9 ms 5244 KB answer = 1
22 Correct 417 ms 183896 KB answer = 358
23 Correct 399 ms 184016 KB answer = 336
24 Correct 406 ms 183500 KB answer = 339
25 Correct 404 ms 184096 KB answer = 357
26 Correct 406 ms 184040 KB answer = 354
27 Correct 391 ms 171536 KB answer = 333
28 Correct 411 ms 173804 KB answer = 314
29 Correct 392 ms 172360 KB answer = 322
30 Correct 397 ms 174532 KB answer = 339
31 Correct 392 ms 171900 KB answer = 351
32 Correct 415 ms 175296 KB answer = 1
33 Correct 434 ms 175172 KB answer = 1
34 Correct 417 ms 174628 KB answer = 1
35 Correct 420 ms 175296 KB answer = 1
36 Correct 413 ms 173740 KB answer = 1
37 Correct 147 ms 13204 KB answer = 1
38 Correct 149 ms 13268 KB answer = 1
39 Correct 145 ms 13232 KB answer = 1
40 Correct 142 ms 13252 KB answer = 1
41 Correct 2110 ms 6492 KB answer = 6296
42 Correct 2127 ms 6484 KB answer = 6267
43 Correct 2011 ms 6636 KB answer = 6264
44 Correct 2053 ms 6604 KB answer = 6384
45 Correct 2093 ms 6752 KB answer = 6272
46 Correct 1994 ms 6640 KB answer = 6177
47 Correct 1991 ms 6700 KB answer = 6144
48 Correct 2073 ms 6784 KB answer = 6272
49 Correct 2007 ms 6836 KB answer = 6241
50 Correct 1970 ms 6608 KB answer = 6169
51 Correct 2091 ms 6460 KB answer = 1
52 Correct 2213 ms 6452 KB answer = 1
53 Correct 2156 ms 6656 KB answer = 1
54 Correct 2079 ms 6468 KB answer = 1
55 Correct 2104 ms 6580 KB answer = 1
56 Correct 2111 ms 6520 KB answer = 1426
57 Correct 2058 ms 6468 KB answer = 1427
58 Correct 2097 ms 6556 KB answer = 1428
59 Correct 2051 ms 6488 KB answer = 1427
60 Execution timed out 6103 ms 186456 KB Time limit exceeded
61 Halted 0 ms 0 KB -