Submission #228735

#	Time	Username	Problem	Language	Result	Execution time	Memory
228735		davitmarg	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4075 ms	129524 KiB

subsequence

/*DavitMarg*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

int n;
int a[N], k[N],cnt[1050];
pair<int, int> d[1050][1050][15], dp[N],ans;

int main()
{
	cin >> 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 mask = 0; mask < (1 << 10); mask++)
		for (int i = 0; i < 10; i++)
			if ((1 << i) & mask)
				cnt[mask]++;

	for (int mask = 0; mask < (1 << 10); mask++)
		for (int mask2 = 0; mask2 < (1 << 10); mask2++)
			for (int i = 0; i <= 10; i++)
				d[mask][mask2][i] = MP(-1, 0);

	for (int i = 1; i <= n; i++)
	{
		dp[i] = MP(1, 0);
		int msk = a[i] >> 10;
		for (int mask = 0; mask < (1 << 10); mask++)
		{
			if (k[i] - cnt[mask & (a[i] % 1024)] >= 0 && k[i] - cnt[mask & (a[i] % 1024)] <= 10)
				dp[i] = max(dp[i], d[mask][msk][k[i] - cnt[mask & (a[i] % 1024)]]);
		}
		for (int mask = 0; mask < (1 << 10); mask++)
			d[a[i] % 1024][mask][cnt[msk & mask]] = max(d[a[i] % 1024][mask][cnt[msk & mask]], MP(dp[i].first + 1, i));
		ans = max(ans, MP(dp[i].first, i));
	}

	vector<int> x;
	x.push_back(ans.second);
	while (dp[ans.second].second)
	{
		ans.second = dp[ans.second].second;
		x.PB(ans.second);
	}
	reverse(all(x));

	cout << x.size() << endl;
	for (int i = 0; i < x.size(); i++)
		printf("%d ", x[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

4
1023 2047 1022 1047552
0 10 10 1

5
5 3 5 3 5
10 1 20 1 20

*/

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++)
                  ~~^~~~~~~~~~
subsequence.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:41: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