Submission #87287

#	Time	Username	Problem	Language	Result	Execution time	Memory
87287		Yaroslaff	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6013 ms	91900 KiB

subsequence

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define it int
#define ld long double
#define endl '\n'
#define TIME 1.0*clock()/CLOCKS_PER_SEC

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int M = 1e9 + 7;
const int N = 1e5 + 7;

it n, x[N], k[N], kol[(1<<10)], dp[(1<<10)][(1<<10)][11], pr[(1<<10)][(1<<10)][11], ans = 0, pos = 0;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    vector<it> p(N, 0), res(N, 1);
    cin >> n;
    for (it i = 1; i <= n; i++)
        cin >> x[i];
    for (it i = 1; i <= n; i++)
        cin >> k[i];
    for (size_t i = 1; i <= n; i++){
        it a = (x[i]>>10);
        it b = x[i] - (a<<10);
        for (size_t j = 0; j < 1024; j++){
            it need = k[i] - __builtin_popcount(b&j);
            if (need >= 0 && need <= 10 && dp[a][j][need] + 1 > res[i])
                res[i] = dp[a][j][need] + 1, p[i] = pr[a][j][need];
        }
        for (size_t j = 0; j < 1024; j++){
            it cur = __builtin_popcount(a&j);
            if (dp[j][b][cur] < res[i])
                dp[j][b][cur] = res[i], pr[j][b][cur] = i;
        }
        if (res[i] > ans)
            ans = res[i], pos = i;
    }
    vector<it> path;
    while (pos){
        path.pb(pos);
        pos = p[pos];
    }
    reverse(path.begin(), path.end());
    cout << path.size() << endl;
    for (auto itt : path) cout << itt << ' ';
    return 0;
}

Compilation message (stderr)

subsequence.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:35:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (size_t i = 1; i <= n; i++){
                        ~~^~~~

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