제출 #440671

#제출 시각아이디문제언어결과실행 시간메모리
440671AutronLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6038 ms88060 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; int last[1<<10][1<<10][21]; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; cin>>n; vector<int> len(n+1), pr(n+1), a(n+1), k(n+1); for(int i=1;i<=n;++i) cin>>a[i]; for(int i=1;i<=n;++i) cin>>k[i]; for(int i=1;i<=n;++i){ int lef=a[i]&((1<<10)-1), rig=a[i]>>10; for(int mask=0;mask<(1<<10);++mask){ int tar=k[i]-__builtin_popcount(mask&lef); auto x=last[mask][rig][tar]; if(0<=tar&&tar<=10&&(len[i]<len[x])){ len[i]=len[x]; pr[i]=x; } } len[i]++; for(int mask=0;mask<(1<<10);++mask){ auto &x=last[lef][mask][__builtin_popcount(mask&rig)]; if(len[x]<len[i]){ x=i; } } } int poz=0; len[0]=-1; for(int i=1;i<=n;++i){ if(len[i]>len[poz]) poz=i; } stack<int> ans; cout<<len[poz]<<"\n"; while(poz){ ans.push(poz); poz=pr[poz]; } while(!ans.empty()) cout<<ans.top()<<" ", ans.pop(); cout<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...