#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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |
- |