Submission #1269397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269397		g4yuhg	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	4069 ms	174064 KiB

subsequence

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "subsequence"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll n, a[N], k[N];

ll trace[N];
ll la[N], bc_high[1024][1024];
pii dp[1024][1024][21];

ll base = (1 << 10) - 1;

void sub3() {
	ll ans = 0, id = 0;
	for (int i = 1; i <= n; i ++) {
		ll res = 0;
		for (int mask = 0; mask < 1024; mask ++) {
			ll k_low = k[i] - __builtin_popcount(mask & (a[i] >> 10));
			if (k_low >= 0 && k_low <= 10) {
				res = max(res, dp[mask][(a[i] & base)][k_low].fi);
				if (res == dp[mask][(a[i] & base)][k_low].fi) {
					trace[i] = dp[mask][(a[i] & base)][k_low].se;
				}
			}
		}
		res ++ ;
		if (res > ans) {
			ans = res;
			id = i;
		}
		for (int mask = 0; mask < 1024; mask ++) {
			ll k_val = __builtin_popcount((a[i] & base) & mask);
			dp[(a[i] >> 10)][mask][k_val] = max(dp[(a[i] >> 10)][mask][k_val], {res, i});
		}
	}
	cout << ans << endl;
	vector<ll> vt;
	while (true) {
		vt.push_back(id);
		id = trace[id];
		if (id == 0) break;
	}
	reverse(vt.begin(), vt.end());
	for (auto it : vt) cout << it << " ";
}

bool klinh;

signed main(void) {
    start;
    faster;
	  
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i ++) {
		cin >> k[i];
	}
	sub3();
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:9:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:63:5: note: in expansion of macro 'start'
   63 |     start;
      |     ^~~~~
subsequence.cpp:9:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:63:5: note: in expansion of macro 'start'
   63 |     start;
      |     ^~~~~

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