Submission #50313

#	Time	Username	Problem	Language	Result	Execution time	Memory
50313		mra2322001	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5649 ms	110696 KiB

subsequence

#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 3;

int n, a[N], k[N], f[1024][1024][11];
int d[N], trace[N];

main(){
    ios_base::sync_with_stdio(0);

    cin >> n;
    f1(i, n) cin >> a[i];
    f1(i, n) cin >> k[i];
    f1(i, n){
        int l = a[i] >> 10;
        int r = 1023 & a[i], best = 0;
        f0(j, 1024){
            int kb = __builtin_popcount(j&r);
            kb = k[i] - kb;
            if(kb < 0 || kb > 10) continue;
            if(d[best] < d[f[l][j][kb]]) best = f[l][j][kb];
        }
        d[i] = d[best] + 1;
        trace[i] = best;
        f0(j, 1024){
            /// f[j][r][kb]
            int kb = __builtin_popcount(l&j);
            if(d[i] > d[f[j][r][kb]]){
                f[j][r][kb] = i;
            }
        }
     }
     int ans = 0;
     f1(i, n) if(d[i] > d[ans]) ans = i;
     cout << d[ans] << endl;
     vector <int> save;
     for(ans; ans > 0; ans = trace[ans]) save.push_back(ans);
     for(int i = save.size() - 1; i >= 0; i--) cout << save[i] << " ";
}

Compilation message (stderr)

subsequence.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:41:13: warning: statement has no effect [-Wunused-value]
      for(ans; ans > 0; ans = trace[ans]) save.push_back(ans);
             ^

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