Submission #1204638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204638		hoa208	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3132 ms	183532 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
#define t_test int t;cin >> t;while(t--)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
inline  void adm(ll &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;}
//--------------------------------------------------------------------
const ll N = 1e5 + 1;
const ll b = 10;
ll n;
ll a[N], k[N];
ll dp[1 << b][1 << b][11], f[1 << b][1 << b][11];
ll trace[N];
void hbmt() {
	ll n;
	cin >> n;
	FOR(i, 1, n) {
		cin >> a[i];
	}
	FOR(i, 1, n) {
		cin >> k[i];
	}
	ll ans = 0, u = 0;
	FOR(i, 1, n) {
		ll pre = a[i] >> b;
		ll suf = a[i] % (1 << b);
		ll res = 1;
		FOR(mask, 0, (1 << b) - 1) {
			ll c = __builtin_popcount(mask & pre);
			if(k[i] >= c && k[i] - c <= 10)
				if(dp[mask][suf][k[i] - c] + 1 > res) {
					res = dp[mask][suf][k[i] - c] + 1;
					trace[i] = f[mask][suf][k[i] - c];
				}
		}
		if(ans < res) {
			ans = res;
			u = i;
		}
		FOR(mask, 0, (1 << b) - 1) {
			ll c = __builtin_popcount(mask & suf);
			if(dp[pre][mask][c] < res) {
				dp[pre][mask][c] = res;
				f[pre][mask][c] = i;
			}
		}
	}
	stack<ll> st;
	while(u != 0) {
		st.push(u);
		u = trace[u];
	}
	cout << ans << '\n';
	while(!st.empty()) {
		cout << st.top() << ' ';
		st.pop();
	}
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	if(fopen("hbmt.inp", "r")) {
		freopen("hbmt.inp", "r", stdin);
		freopen("hbmt.out", "w", stdout);
	}
	
	// t_test 
	hbmt();
	return 0;
}

Compilation message (stderr)

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

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