Submission #343366

#TimeUsernameProblemLanguageResultExecution timeMemory
343366ivan_tudorLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
2 ms492 KiB
#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(rsp[i] < rsp[ dp[mask][rms][mr] ]){
        rsp[i] = rsp[ dp[mask][rms][mr]];
        lst[i] = lst[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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...