제출 #518946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518946		shmad	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6020 ms	4000 KiB

subsequence

        #pragma GCC optimize("O3", "unroll-loops")
        #pragma GCC target("sse", "sse2", "sse3", "sse4", "avx2", "bmi", "bmi2", "lzcnt", "popcnt") 
         
        #include <bits/stdc++.h>
             
            #define int long long
            #define vt vector
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define sz(x) (int)(x).size()
            #define ff first
            #define ss second
            #define dbg(x) cerr << #x << " = " << x << '\n'
             
            using namespace std;
            using ll = long long;
            using pii = pair<int, int>;
            using vvi = vt< vt<int> >;
             
            const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
            const double eps = 1e-6;
             
            int dp[N], p[N];
             
            void solve () {
            	int n;
            	cin >> n;
            	vt<int> a(n + 1), k(n + 1);
            	for (int i = 1; i <= n; i++) cin >> a[i];
            	for (int i = 1; i <= n; i++) cin >> k[i];
            	int res = 0, ps = 0;
            	for (int i = 1; i <= n; i++) {
            		dp[i] = 1;
            		for (int j = 1; j < i; j++) {
            			if (__builtin_popcount(a[i] & a[j]) != k[i]) continue;
            			if (dp[i] < dp[j] + 1) {
            				dp[i] = dp[j] + 1;
            				p[i] = j;
            			}
            		}
            		if (dp[i] > res) res = dp[i], ps = i;
            	}
            	cout << res << '\n';
            	vt<int> ans;
            	while (ps) {
            		ans.pb(ps);
            		ps = p[ps];
            	}
            	reverse(all(ans));
            	for (auto x: ans) cout << x << ' ';
            	cout << '\n';
            }
             
            bool testcases = 0;
                              
            signed main() {
                cin.tie(0) -> sync_with_stdio(0);
                int test = 1;
                if (testcases) cin >> test;
                for (int cs = 1; cs <= test; cs++) {
                    solve();
                }
            }

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