이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
const int M=(1<<10);
pair<int,int>dp[M][M][10];///{score,index} [fixed left][supposed right][common right with supposed right]
int previous[N+1];
int main() {
int n;
cin>>n;
int a[n+1];
int k[n+1];
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=1; i<=n; i++)cin>>k[i];
pair<int,int>ans;
for(int i=1; i<=n; i++) {
pair<int,int>curans= {0,0};
int left=(a[i]>>10),right=a[i]&((1<<10)-1);
for(int j=0; j<M; j++) {
int rem=k[i]-__builtin_popcount(j&left);
if(rem<0 || rem>10)continue;
curans=max(curans,dp[j][right][rem]);
}
curans.first++;
previous[i]=curans.second;
curans.second=i;
ans=max(ans,curans);
for(int j=0;j<M;j++) {
int x=__builtin_popcount(j&right);
dp[left][j][x]=max(dp[left][j][x],curans);
}
}
int cur=ans.second;
vector<int>anss;
while(cur>0) {
anss.push_back(cur);
cur=previous[cur];
}
reverse(anss.begin(),anss.end());
cout<<anss.size()<<endl;
for(int i:anss)cout<<i<<' ';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |