제출 #92391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92391		davitmarg	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6094 ms	11260 KiB

subsequence

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

LL bitCount(LL n)
{
	LL res = 0;
	while (n)
	{
		if (n & 1)
			res++;
		n >>= 1;
	}
	return res;
}

LL bitCount(LL a, LL b)
{
	return bitCount( (a&b) );
}

LL n, a[100005], k[100005],dp[100005],prv[100005],last[(1<<20)+10],mx;

vector<LL> ans;

int main()
{
	cin >> n;
	for (LL i = 1; i <= n; i++)
	{
		cin >> a[i];
		mx = max(mx,a[i]);
	}
	for (LL i = 1; i <= n; i++)
		cin >> k[i];

	for (LL i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (LL j = 0; j <= mx; j++)
			if (last[j] != 0 && bitCount(a[i], j) == k[i] && dp[i] <= 1 + dp[last[j]])
			{
				dp[i] = 1 + dp[last[j]];
				prv[i] = last[j];
			}
		if (dp[last[a[i]]] < dp[i])
			last[a[i]] = i;
	}

	mx = 0;
	for (LL i = 1; i <= n; i++)
		mx = max(dp[i], mx);
	for (LL i = 1; i <= n; i++)
		if (dp[i] == mx)
		{
			while (i)
			{
				ans.PB(i);
				i = prv[i];
			}
			break;
		}

	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for (LL i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	cout << endl;
	return 0;
}

/*


11 
5 5 13 17 7 17 5 5 1 5 5
2 2 2  1  2  2 1 1 1 1 2


7
5 5 13 17 7 17 5 
2 2 2  1  2  1 1 

2
8 9
20 0

5
5 3 5 3 5 
10 1 20 1 20

4
1 2 3 4 
10 0 1 0

*/

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp: In function 'int main()':
subsequence.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (LL i = 0; i < ans.size(); i++)
                 ~~^~~~~~~~~~~~

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