제출 #1102417

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

subsequence

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __builtin_popcount __builtin_popcountll
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
template <class T, class T2> ostream &operator<<(ostream &o, pair<T, T2> p)
{
    o << "(" << p.first << ", " << p.second << ")"; 
    return o;
}
const int M = 5003;
int a[M], trace[M], f[M], cnt[M];


signed main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> cnt[i];
    for (int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for (int j = 1; j < i; ++j)
        {
            if (cnt[i] == __builtin_popcount(a[i] & a[j]) && f[i] < f[j] + 1)
            {
                trace[i] = j;
                f[i] = f[j] + 1;
            }
        }
    }
    int pos = max_element(f + 1, f + n + 1) - f;
    cout << f[pos] << "\n";
    vector <int> res;
    while (pos)
    {
        res.push_back(pos);
        pos = trace[pos];
    }
    reverse(res.begin(), res.end());
    for (auto it: res)
        cout << it << " ";
}

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