oj.uz

Submission #474056

# Submission time Handle Problem Language Result Execution time Memory
474056 2021-09-16T18:21:02 Z ogibogi2004 Longest beautiful sequence (IZhO17_subsequence) C++14
40 / 100
 6000 ms 187380 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()
{
    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<<endl;
    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<<endl;
return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB answer = 4
2 Correct 6 ms 4940 KB answer = 1
3 Correct 8 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 5208 KB answer = 1
7 Correct 6 ms 5036 KB answer = 1
8 Correct 13 ms 7204 KB answer = 3
9 Correct 13 ms 7040 KB answer = 2
10 Correct 13 ms 7036 KB answer = 3
11 Correct 12 ms 6988 KB answer = 2
12 Correct 13 ms 7372 KB answer = 3
13 Correct 13 ms 6860 KB answer = 2
14 Correct 13 ms 6732 KB answer = 1
15 Correct 14 ms 7360 KB answer = 1
16 Correct 16 ms 7372 KB answer = 1
17 Correct 14 ms 6860 KB answer = 1
18 Correct 10 ms 5268 KB answer = 1
19 Correct 10 ms 5284 KB answer = 1
20 Correct 10 ms 5116 KB answer = 1
21 Correct 10 ms 5248 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB answer = 4
2 Correct 6 ms 4940 KB answer = 1
3 Correct 8 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 5208 KB answer = 1
7 Correct 6 ms 5036 KB answer = 1
8 Correct 13 ms 7204 KB answer = 3
9 Correct 13 ms 7040 KB answer = 2
10 Correct 13 ms 7036 KB answer = 3
11 Correct 12 ms 6988 KB answer = 2
12 Correct 13 ms 7372 KB answer = 3
13 Correct 13 ms 6860 KB answer = 2
14 Correct 13 ms 6732 KB answer = 1
15 Correct 14 ms 7360 KB answer = 1
16 Correct 16 ms 7372 KB answer = 1
17 Correct 14 ms 6860 KB answer = 1
18 Correct 10 ms 5268 KB answer = 1
19 Correct 10 ms 5284 KB answer = 1
20 Correct 10 ms 5116 KB answer = 1
21 Correct 10 ms 5248 KB answer = 1
22 Correct 421 ms 183816 KB answer = 358
23 Correct 412 ms 184004 KB answer = 336
24 Correct 414 ms 183432 KB answer = 339
25 Correct 408 ms 184260 KB answer = 357
26 Correct 409 ms 183988 KB answer = 354
27 Correct 402 ms 171504 KB answer = 333
28 Correct 403 ms 173816 KB answer = 314
29 Correct 397 ms 172460 KB answer = 322
30 Correct 408 ms 174276 KB answer = 339
31 Correct 400 ms 171840 KB answer = 351
32 Correct 415 ms 175336 KB answer = 1
33 Correct 424 ms 175184 KB answer = 1
34 Correct 420 ms 174516 KB answer = 1
35 Correct 448 ms 175368 KB answer = 1
36 Correct 422 ms 173660 KB answer = 1
37 Correct 157 ms 13256 KB answer = 1
38 Correct 160 ms 13256 KB answer = 1
39 Correct 157 ms 13236 KB answer = 1
40 Correct 157 ms 13328 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB answer = 4
2 Correct 6 ms 4940 KB answer = 1
3 Correct 8 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 5208 KB answer = 1
7 Correct 6 ms 5036 KB answer = 1
8 Correct 13 ms 7204 KB answer = 3
9 Correct 13 ms 7040 KB answer = 2
10 Correct 13 ms 7036 KB answer = 3
11 Correct 12 ms 6988 KB answer = 2
12 Correct 13 ms 7372 KB answer = 3
13 Correct 13 ms 6860 KB answer = 2
14 Correct 13 ms 6732 KB answer = 1
15 Correct 14 ms 7360 KB answer = 1
16 Correct 16 ms 7372 KB answer = 1
17 Correct 14 ms 6860 KB answer = 1
18 Correct 10 ms 5268 KB answer = 1
19 Correct 10 ms 5284 KB answer = 1
20 Correct 10 ms 5116 KB answer = 1
21 Correct 10 ms 5248 KB answer = 1
22 Correct 421 ms 183816 KB answer = 358
23 Correct 412 ms 184004 KB answer = 336
24 Correct 414 ms 183432 KB answer = 339
25 Correct 408 ms 184260 KB answer = 357
26 Correct 409 ms 183988 KB answer = 354
27 Correct 402 ms 171504 KB answer = 333
28 Correct 403 ms 173816 KB answer = 314
29 Correct 397 ms 172460 KB answer = 322
30 Correct 408 ms 174276 KB answer = 339
31 Correct 400 ms 171840 KB answer = 351
32 Correct 415 ms 175336 KB answer = 1
33 Correct 424 ms 175184 KB answer = 1
34 Correct 420 ms 174516 KB answer = 1
35 Correct 448 ms 175368 KB answer = 1
36 Correct 422 ms 173660 KB answer = 1
37 Correct 157 ms 13256 KB answer = 1
38 Correct 160 ms 13256 KB answer = 1
39 Correct 157 ms 13236 KB answer = 1
40 Correct 157 ms 13328 KB answer = 1
41 Correct 1824 ms 7208 KB answer = 6296
42 Correct 2029 ms 7060 KB answer = 6267
43 Correct 2122 ms 7052 KB answer = 6264
44 Correct 2081 ms 7208 KB answer = 6384
45 Correct 2151 ms 7052 KB answer = 6272
46 Correct 2163 ms 7104 KB answer = 6177
47 Correct 2092 ms 7216 KB answer = 6144
48 Correct 2021 ms 7192 KB answer = 6272
49 Correct 2215 ms 7108 KB answer = 6241
50 Correct 2061 ms 7268 KB answer = 6169
51 Correct 2220 ms 7092 KB answer = 1
52 Correct 2119 ms 7092 KB answer = 1
53 Correct 2134 ms 7224 KB answer = 1
54 Correct 2191 ms 7084 KB answer = 1
55 Correct 2154 ms 7092 KB answer = 1
56 Correct 2095 ms 7108 KB answer = 1426
57 Correct 2064 ms 7212 KB answer = 1427
58 Correct 1841 ms 7016 KB answer = 1428
59 Correct 2119 ms 7312 KB answer = 1427

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB answer = 4
2 Correct 6 ms 4940 KB answer = 1
3 Correct 8 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 5208 KB answer = 1
7 Correct 6 ms 5036 KB answer = 1
8 Correct 13 ms 7204 KB answer = 3
9 Correct 13 ms 7040 KB answer = 2
10 Correct 13 ms 7036 KB answer = 3
11 Correct 12 ms 6988 KB answer = 2
12 Correct 13 ms 7372 KB answer = 3
13 Correct 13 ms 6860 KB answer = 2
14 Correct 13 ms 6732 KB answer = 1
15 Correct 14 ms 7360 KB answer = 1
16 Correct 16 ms 7372 KB answer = 1
17 Correct 14 ms 6860 KB answer = 1
18 Correct 10 ms 5268 KB answer = 1
19 Correct 10 ms 5284 KB answer = 1
20 Correct 10 ms 5116 KB answer = 1
21 Correct 10 ms 5248 KB answer = 1
22 Correct 421 ms 183816 KB answer = 358
23 Correct 412 ms 184004 KB answer = 336
24 Correct 414 ms 183432 KB answer = 339
25 Correct 408 ms 184260 KB answer = 357
26 Correct 409 ms 183988 KB answer = 354
27 Correct 402 ms 171504 KB answer = 333
28 Correct 403 ms 173816 KB answer = 314
29 Correct 397 ms 172460 KB answer = 322
30 Correct 408 ms 174276 KB answer = 339
31 Correct 400 ms 171840 KB answer = 351
32 Correct 415 ms 175336 KB answer = 1
33 Correct 424 ms 175184 KB answer = 1
34 Correct 420 ms 174516 KB answer = 1
35 Correct 448 ms 175368 KB answer = 1
36 Correct 422 ms 173660 KB answer = 1
37 Correct 157 ms 13256 KB answer = 1
38 Correct 160 ms 13256 KB answer = 1
39 Correct 157 ms 13236 KB answer = 1
40 Correct 157 ms 13328 KB answer = 1
41 Correct 1824 ms 7208 KB answer = 6296
42 Correct 2029 ms 7060 KB answer = 6267
43 Correct 2122 ms 7052 KB answer = 6264
44 Correct 2081 ms 7208 KB answer = 6384
45 Correct 2151 ms 7052 KB answer = 6272
46 Correct 2163 ms 7104 KB answer = 6177
47 Correct 2092 ms 7216 KB answer = 6144
48 Correct 2021 ms 7192 KB answer = 6272
49 Correct 2215 ms 7108 KB answer = 6241
50 Correct 2061 ms 7268 KB answer = 6169
51 Correct 2220 ms 7092 KB answer = 1
52 Correct 2119 ms 7092 KB answer = 1
53 Correct 2134 ms 7224 KB answer = 1
54 Correct 2191 ms 7084 KB answer = 1
55 Correct 2154 ms 7092 KB answer = 1
56 Correct 2095 ms 7108 KB answer = 1426
57 Correct 2064 ms 7212 KB answer = 1427
58 Correct 1841 ms 7016 KB answer = 1428
59 Correct 2119 ms 7312 KB answer = 1427
60 Execution timed out 6060 ms 187380 KB Time limit exceeded
61 Halted 0 ms 0 KB -