Submission #1085894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085894		serpent_121	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3059 ms	93632 KiB

subsequence

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <numeric>
#include <cmath>
#include <cstring>
#include <climits>
#include <stack>
#include <math.h>
#include <iomanip>
#include <bitset>
typedef long long ll;
using namespace std;
#define fst first
#define snd second
#define pll pair<ll,ll>
// https://oj.uz/problem/view/IZhO17_subsequence

struct State {
    int len;
    int end;
} dp[(1<<10)][(1<<10)][11];
int main() {
   ll n; cin >> n; ll a[n]; ll k[n];
   for (int i = 0; i < n; i++) cin >> a[i];
   for (int i = 0; i<n; i++) cin >> k[i];

   auto left = [](ll b) ->ll {
        return (b >>10);
   };
   auto right = [](ll b) -> ll {
    return (b % (1 << 10));
   };

    int prev[n];
   int ans = 1; int best_i = 0;
   for (int i = 0; i < n; i++) {
        int lbs  = 1;  prev[i] = -1;
        for (int l = 0; l < (1<<10); l++) {
            ll c = __builtin_popcount(l & left(a[i]));
            if (c<= k[i] && k[i]-c <=10) {
                if (lbs < dp[l][right(a[i])][k[i]-c].len + 1) {
                    lbs = dp[l][right(a[i])][k[i]-c].len + 1;
                    prev[i] = dp[l][right(a[i])][k[i]-c].end;
                }
            }
        }
        if (ans < lbs) {
            ans = lbs;
            best_i = i;

        }
        for (int r = 0; r < (1<<10); r++) {
            ll c = __builtin_popcount(r & right(a[i]));
            if ( lbs > dp[left(a[i])][r][c].len) {
                dp[left(a[i])][r][c].len = lbs;
                dp[left(a[i])][r][c].end = i;
            }
        }
   }
   stack<int> s;
   while (best_i!=-1) {
    s.push(best_i);
    best_i = prev[best_i];
   }
   cout << ans << '\n';
   while (!s.empty()) {
    cout << s.top() + 1 << " ";
    s.pop();
   }

   
}

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