Submission #831614

#	Time	Username	Problem	Language	Result	Execution time	Memory
831614		Chal1shkan	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	0 ms	340 KiB

subsequence

//Bismillahir-Rahmanir-Rahim

# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
# define pii pair <int, int>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e5 + 3;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, a[maxn], k[maxn];
ll dp[maxn];
ll par[maxn];

void ma1n (/* SABR */) {
	cin >> n;
	for (ll i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (ll i = 1; i <= n; ++i) {
		cin >> k[i];
	}
	ll best = -1, opt = -1;
	for (ll i = 2; i <= n; ++i) {
		for (ll j = i - 1; j >= 1; --j) {
			if (__builtin_popcount((a[j] & a[i])) == k[i]) {
				if (dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					par[i] = j;
				}
			}
		}
		if (dp[i] > best) {
			best = dp[i];
			opt = i;
		}
	}
	vector <ll> ans;
	while (opt != 0) {
		ans.pb(opt);
		opt = par[opt];
	}
	reverse(all(ans));
	cout << sz(ans) << nl;
	for (ll x : ans) cout << x << ' ';
	
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test) {
//      cout << "Case " << test << ":" << '\n';
        ma1n();
    }
    return 0;
}

// 998batrr | BbIWEJI 3A TObOU!!!
// tourist  | BbIWEJI 3A TObOU!!!

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