Submission #38276

#	Time	Username	Problem	Language	Result	Execution time	Memory
38276		Talant	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5506 ms	108060 KiB

subsequence

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e6 + 1;
const int M = (int)1024;

int n;
int a[N],b[N],bit[N];
int m = 0;
pair<int,int> dp[1025][1025][11];
int p[N];
int nn;

int main () {
        scanf ("%d", &n);

        for (int i = 1; i <= n; i ++)
                scanf ("%d", &a[i]);

        for (int j = 1; j <= n; j ++)
                scanf ("%d", &b[j]);

        for (int i = 0; i <= M; i ++)
                bit[i] = __builtin_popcount(i);

        for (int i = 1; i <= n; i ++) {
                int pr = (a[i] >> 10),sf = (a[i] % M),mx = 1,id = -1;

                for (int j = 0; j < M; j ++) {
                        int cnt = b[i] - bit[j & pr];

                        if (cnt < 0 || cnt > 10)
                                continue;

                        if (mx < dp[j][sf][cnt].fr + 1)
                                mx = dp[j][sf][cnt].fr + 1,id = dp[j][sf][cnt].sc;
                }
                p[i] = id;

                for (int j = 0; j < M; j ++) {
                        int cnt = bit[j & sf];
                        if (dp[pr][j][cnt].fr < mx)
                                dp[pr][j][cnt] = mk(mx,i);
                }
                if (m < mx)
                        m = mx,nn = i;
        }
        cout << m << endl;

        deque <int> dq;

        while (nn != -1) {
                dq.push_front(nn);
                nn = p[nn];
        }
        for (int i = 0; i < dq.size(); i ++)
                cout << dq[i] << " ";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < dq.size(); i ++)
                           ^
subsequence.cpp:25:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &n);
                         ^
subsequence.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", &a[i]);
                                    ^
subsequence.cpp:31:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", &b[j]);
                                    ^

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