제출 #89986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89986		Bodo171	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6042 ms	177864 KiB

subsequence

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=(1<<17);
const int valmax=(1<<20)+1;
const int lim=(1<<10);
vector<int> seq;
int dp[22][valmax][12];
int v[nmax],k[nmax],best[nmax];
int pc[(1<<20)+5];
int n,i,j,ans,curr;
void ins(int x,int val)
{
    for(int i=0;i<lim;i++)
        dp[pc[x]][(x^i)][pc[i]]=max(dp[pc[x]][(x^i)][pc[i]],val);
}
int gt(int x,int b,int btot)
{
    int ret=0;
    int st=max(0,2*b-btot);
    int dr=min(20,20-btot+2*b);
    for(int j=st;j<=dr;j++)
     for(int i=0;i<lim;i++)
            if(btot+j-pc[i]-2*b>=0&&btot+j-pc[i]-2*b<=10)
               ret=max(ret,dp[j][(x^(i<<10))][btot+j-pc[i]-2*b]);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<(1<<20);i++)
       pc[i]=pc[(i&(i-1))]+1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(i=1;i<=n;i++)
    {
        cin>>k[i];
    }
    for(int cnt=1;cnt<=n;cnt++)
    {
        best[cnt]=gt(v[cnt],k[cnt],pc[v[cnt]])+1;
        ins(v[cnt],best[cnt]);
        ans=max(ans,best[cnt]);
        if(ans==best[cnt])
            curr=cnt;
    }
    cout<<ans<<'\n';
    seq.push_back(curr);
    int act=curr;
    for(i=act-1;i>=1;i--)
    {
        if(best[i]==best[curr]-1&&pc[(v[i]&v[curr])]==k[curr])
        {
            seq.push_back(i);
            curr=i;
        }
    }
    reverse(seq.begin(),seq.end());
    for(int i=0;i<seq.size();i++)
        cout<<seq[i]<<' ';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp: In function 'int main()':
subsequence.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<seq.size();i++)
                 ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60