Submission #343370

#	Time	Username	Problem	Language	Result	Execution time	Memory
343370		ivan_tudor	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4561 ms	47848 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
int dp[1030][15][1030];
const int N = 1e5 + 5;
int v[N];
int k[N];
int rsp[N], lst[N];
void print(int nod){
  if(nod == 0)
    return;
  print(lst[nod]);
  cout<<nod<<" ";
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i<=n;i++){
    cin>>v[i];
  }
  for(int i=1;i<=n;i++){
    cin>>k[i];
  }
  int pans = 0;
  for(int i =1; i<=n;i++){
    int mr = v[i] & ((1<<10) - 1);
    int ml = v[i]>>10;
    for(int mask = 0; mask < (1<<10);mask ++){
      int rms = k[i] - __builtin_popcount(mask & ml);
      if(rms > 10 || rms < 0)
        continue;
      if(rsp[i] < rsp[ dp[mask][rms][mr] ]){
        rsp[i] = rsp[ dp[mask][rms][mr]];
        lst[i] = dp[mask][rms][mr];
      }
    }
    rsp[i] ++;
    for(int mask =0 ; mask < (1<<10); mask++){
      int nr = __builtin_popcount(mask & mr);
      int &cur = dp[ml][nr][mask];
      if(rsp[cur] < rsp[i])
        cur = i;
    }
    if(rsp[i]  > rsp[pans])
      pans = i;
  }
  cout<<rsp[pans]<<"\n";
  print(pans);
  return 0;
}

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