| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 658888 | ono_de206 | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
//#define int long long
template<typename T>
void mxx(T &a, T b){if(b>a) a=b;}
template<typename T>
void mnn(T &a, T b){if(b<a) a=b;}
const int mxn=11,mxxa=1e5+10;
int dp[1<<mxn][1<<mxn][mxn];
int cm[mxxa],dd[mxxa];
int bb[1<<mxn][1<<mxn];
int a[mxxa],k[mxxa];
signed main(){
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>k[i];
for(int i=0; i<(1<<10); i++){
for(int j=0; j<(1<<10); j++){
int a=(i&j);
bb[i][j]=__builtin_popcount(i,j);
}
}
for(int i=1; i<=n; i++){
int l=(a[i]>>10);
int r=((l<<10)^a[i]);
for(int j=0; j<(1<<10); j++){
int cnt=bb[l][j];
if(cnt>k[i]) continue;
cnt=k[i]-cnt;
int idx=dp[j][r][cnt];
if(dd[i]<dd[idx]+1){
dd[i]=dd[idx]+1;
cm[i]=idx;
}
}
for(int j=0; j<(1<<10); j++){
int cnt=bb[j][r];
int &idx=dp[l][j][cnt];
if(dd[idx]<dd[i]){
idx=i;
}
}
}
pair<int,int> mx;
mx=make_pair(0,0);
for(int i=1; i<=n; i++){
mxx(mx,{dd[i],i});
}
vector<int> ans;
int idx=mx.second;
while(idx){
ans.pb(idx);
idx=cm[idx];
}
sort(all(ans));
cout<<(int)ans.size()<<'\n';
for(int x : ans) cout<<x<<' ';
cout<<'\n';
return 0;
}