| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 527784 | rsjw | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <algorithm>
const int maxcount = 10;
const int mask = 1 << maxcount;
const int maxn = 100005;
using namespace std;
int cnt[mask];
int a[maxn],k[maxn];
int f[mask][mask][maxcount+1];
int id[mask][mask][maxcount+1];
int last[maxn];
int n;
vector<int> sol;
int main() {
//freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<mask; i++) cnt[i]=cnt[i>>1]+(i&1);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) scanf("%d",&k[i]);
int ans,cur0,cur1,bc;
int maxid,maxn=0;
for(int i=1; i<=n; i++) {
cur0=(a[i])>>maxcount,cur1=(a[i])&(mask-1);
ans=0;
for(int pre1=0;pre1<mask;pre1++) {
bc=k[i]-cnt[pre1&cur1];
if(ans<=f[pre1][cur0][bc]) ans=f[pre1][cur0][bc]+1,last[i]=id[pre1][cur0][bc];
}
for(int nex0=0;nex0<mask;nex0++) {
bc=cnt[nex0&cur0];
if(ans>f[cur1][nex0][bc]) f[cur1][nex0][bc]=ans,id[cur1][nex0][bc]=i;
}
if(maxn<ans) {
maxn=ans;
maxid=i;
}
}
int x=maxid;
while(x) sol.push_back(x),x=last[x];
sort(sol.begin(),sol.end());
printf("%d\n",(int)sol.size());
for(auto i:sol) {
printf("%d ",i);
}
return 0;
}