Submission #472433

#	Time	Username	Problem	Language	Result	Execution time	Memory
472433		Shin	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5980 ms	48324 KiB

subsequence

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

#define right __right
#define left __left

int get_right(int mask) {
    return mask & (MASK(10) - 1);
}
int get_left(int mask) {
    return mask >> 10;
}

int cnt_bit(int mask) {
    return __builtin_popcount(mask);
}

int n;
int a[N];
int k[N];
int best[N];
int trace[N];
int dp[MASK(10)][MASK(10)][11];
    
void solve(void) { 
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++) scanf("%d", &k[i]);
    

    for (int i = 1; i <= n; i ++) {
        int left = get_left(a[i]);
        int right = get_right(a[i]);

        for (int mask = 0; mask < MASK(10); mask ++) {
            int need = k[i] - cnt_bit(right & mask);
            if (0 > need || need > 10) continue;
            if (maximize(best[i], best[dp[left][mask][need]])) {
                trace[i] = dp[left][mask][need];
            }
        }

        best[i] ++;
        for (int mask = 0; mask < MASK(10); mask ++) {
            int cntbit = cnt_bit(mask & left);
            if (best[i] > best[dp[mask][right][cntbit]])
                dp[mask][right][cntbit] = i;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) if (best[i] > best[res])
        res = i;

    vector<int> idx;
    for (int i = res; i; i = trace[i]) idx.push_back(i);
    printf("%d\n", (int) idx.size());
    reverse(all(idx));
    for (int i: idx) printf("%d ", i);    
}

int main(void) {
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
subsequence.cpp:50:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
      |                                   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:51:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for (int i = 1; i <= n; i ++) scanf("%d", &k[i]);
      |                                   ~~~~~^~~~~~~~~~~~~

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