Submission #35051

#	Time	Username	Problem	Language	Result	Execution time	Memory
35051		model_code	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4316 ms	56972 KiB

subsequence

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()

const int inf = (1ll << 30) - 1;
const int maxn = (int) 1e5 + 10;

using namespace std;

int dp[(1<<20)+ 10][10 + 3];
int a[100100];
int prv[100100];
int k[100100];
int mx[100100];
int cnt[(1<<10) + 10];
int n;
void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; i++){
		scanf("%d", &k[i]);
	}
	for(int i = 0; i < (1<<10); i++)
		cnt[i] = __builtin_popcount(i);

	for(int i = 1; i <= n; ++i){
		int x = a[i] & ((1<<10)-1);
		int y = (a[i] >> 10) & ((1<<10)-1);
		int &cur = mx[i];
		int &ind = prv[i];
		for(int mask = 0; mask < (1<<10); mask++){
			int K = k[i] - cnt[mask & y];
			if(K < 0 || K > 10) continue;
			int &cc = dp[(mask<<10)|x][K];
			if(mx[cc] > cur){
				cur = mx[cc];
				ind = cc;
			}
		}
		cur++;
		
		for(int mask = 0; mask < (1<<10); ++mask){
			int K = cnt[mask & x];
			int &cc = dp[(y<<10)|mask][K];
			if(mx[cc] < cur){
				cc = i;
			}
		}
	}
	int j = 0;
	for(int i = 1; i <= n; i++){
		if(mx[j] < mx[i]){
			j = i;
		}
	}
	vector<int> ans;
	while(j){
		ans.pb(j);
		j = prv[j];
	}
	reverse(all(ans));
	printf("%d\n", ans.size());
	for(int i = 0; i < ans.size(); i++){
		if(i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}

int main () {
    int t=1;
    //scanf("%d", &t);
    for(int i=1; i <= t; i++){
      //printf("Case #%d\n", i);
      solve();
    }

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:84:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                           ^
subsequence.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); i++){
                   ^
subsequence.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:40:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
subsequence.cpp:43:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k[i]);
                     ^

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