Submission #36928

#	Time	Username	Problem	Language	Result	Execution time	Memory
36928		top34051	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5229 ms	48780 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 1e5 + 5;
const int cut = 1024;

int n;
int p[maxn], k[maxn];
int cnt[cut];
int dp[maxn], rec[cut][cut][11];
int track[maxn];
vector<int> res;

int main() {
    int i,x,y,a,b;
    pii ans;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&p[i]);
    for(i=1;i<=n;++i) scanf("%d",&k[i]);
    for(x=0;x<cut;++x) cnt[x] = __builtin_popcount(x);
    ans = {0,0};
    for(i=1;i<=n;++i) {
        a = p[i]>>10; b = p[i]%cut; dp[i] = 1;
        //fix C (x)
        for(x=0;x<cut;++x) {
            int want = k[i] - cnt[a&x];
            if(want<0 || want>10) continue;
            int pos = rec[x][b][want];
            if(dp[i] < dp[pos] + 1) dp[i] = dp[pos] + 1, track[i] = pos;
        }
        if(ans.X < dp[i]) ans = make_pair(dp[i], i);
        //fix B (x)
        for(x=0;x<cut;++x) {
            int want = cnt[b&x];
            int pos = rec[a][x][want];
            if(dp[pos] < dp[i]) rec[a][x][want] = i;
        }
    }
    printf("%d\n",ans.X);
    x = ans.Y;
    while(x) res.emplace_back(x), x = track[x];
    reverse(res.begin(), res.end());
    for(auto t : res) printf("%d ",t);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:19:13: warning: unused variable 'y' [-Wunused-variable]
     int i,x,y,a,b;
             ^
subsequence.cpp:21:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
subsequence.cpp:22:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;++i) scanf("%d",&p[i]);
                                        ^
subsequence.cpp:23:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;++i) scanf("%d",&k[i]);
                                        ^

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