Submission #167757

#	Time	Username	Problem	Language	Result	Execution time	Memory
167757		abil	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3831 ms	93152 KiB

subsequence

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e5 + 12);
const int m = (1 << 10);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

pair<int,int > dp[m][m][11];
int a[N], path[N], k[N], bit[m];
main()
{
	int n;
	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 < m; i++){
		bit[i] = __builtin_popcount(i);
	}
	int ans = 0, ansid;
	for(int i = 1;i <= n; i++){
		int pr = (a[i] >> 10);
		int sf = (a[i] % m);
		int mx = 1, id = 0;
		for(int j = 0;j < m; j++){
			int need = k[i] - bit[j & pr];
			if(need < 0 || need > 10){
				continue;
			}
			if(mx < dp[j][sf][need].fr + 1){
				mx = dp[j][sf][need].fr + 1;
				id = dp[j][sf][need].sc;
			}
		}
		path[i] = id;
		for(int j = 0;j < m; j++){
			int need = bit[j & sf];
			if(dp[pr][j][need].fr < mx){
				dp[pr][j][need] = {mx,i};
			}
		}
		if(mx > ans){
			ans = mx;
			ansid = i;
		}
	}
	printf("%d\n", ans);
	vector<int > vec;
	while(ansid){
		vec.pb(ansid);
		ansid = path[ansid];
	}
	reverse(all(vec));
	for(auto to : vec){
		printf("%d ", to);
	}
}

Compilation message (stderr)

subsequence.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
subsequence.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:27:8: 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