Submission #299773

#	Time	Username	Problem	Language	Result	Execution time	Memory
299773		BeanZ	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2876 ms	93360 KiB

subsequence

// I_LOVE_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define endl '\n'
const int N = 1e5 + 5;
ll a[N], k[N], dp[1025][1025][11], pc[1025], p[1025][1025][11], par[N];
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.ans", "w", stdout);
        }
        ll n;
        cin >> n;
        ll ans = 0;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> k[i];
        for (int i = 0; i < (1 << 10); i++) pc[i] = __builtin_popcount(i);
        ll cur = 0;
        for (int i = 1; i <= n; i++){
                ll x = 0;
                par[i] = -1;
                for (int j = 0; j < (1 << 10); j++){
                        ll rem = k[i] - pc[j & (a[i] >> 10)];
                        if (rem < 0 || rem > 10) continue;
                        if (x < dp[j][a[i] & 1023][rem]){
                                x = dp[j][a[i] & 1023][rem];
                                par[i] = p[j][a[i] & 1023][rem];
                        }
                }
                x++;
                for (int j = 0; j < (1 << 10); j++){
                        if (dp[a[i] >> 10][j][pc[j & a[i]]] < x){
                                dp[a[i] >> 10][j][pc[j & a[i]]] = x;
                                p[a[i] >> 10][j][pc[j & a[i]]] = i;
                        }
                }
                if (ans < x){
                        ans = x;
                        cur = i;
                }
        }
        cout << ans << endl;
        vector<ll> mem;
        mem.push_back(cur);
        while (ans > 1){
                cur = par[cur];
                mem.push_back(cur);
                ans--;
        }
        reverse(mem.begin(), mem.end());
        for (auto j : mem) cout << j << " ";
}
/*
5
5 3 5 3 5
10 1 20 1 20

4
1 2 3 4
10 0 1 0

2
8 9
20 0
*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |                 freopen("test.ans", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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