Submission #1169271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169271		wojtekmal	Jelly Flavours (IOI20_jelly)	C++20	0 / 100	1 ms	328 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>

bool is_better(pll a, pll b)
{
	return a.first <= b.first && a.second <= b.second;
}

int find_maximum_unique(int x, int y, std::vector<int> A, std::vector<int> B)
{
	int n = A.size();
	
	if (x <= 500 && y <= 500 && n <= 200)
	{
		array<set<pll>, 201> best{};
		best[0].insert({0, 0});

		for (int i = 0; i < n; i++)
		{
			//cout << "jelly index: " << i << "\n";
			ll a = A[i];
			ll b = B[i];
			
			for (int prev_count = 0; prev_count <= i; prev_count++)
			{
				for (pll option : {pll{0, b}, pll{a, 0}})
				{
					for (pll base : best[prev_count])
					{
						pll choice = {option.first + base.first, option.second + base.second};
						//cout << "choice: " << choice.first << " " << choice.second << "\n";
						if (choice.first > x || choice.second > y)
						{
							//cout << "not affordable\n";
							continue;
						}

						auto it = best[prev_count + 1].insert(choice).first;
						
						while (true)
						{
							if (next(it) == best[prev_count + 1].end()) break;
							auto after = next(it);
							if (!is_better(*after, choice)) break;
							//cout << "erasing 1\n";
							best[prev_count + 1].erase(after);
						}

						while (true)
						{
							if (it == best[prev_count + 1].begin()) break;
							auto before = prev(it);
							if (!is_better(*before, choice)) break;
							//cout << "*before, choice: " << before->first << " " << before->second << " " << choice.first << " " << choice.second << "\n";
							//cout << (before->first <= choice.first && before->second <= choice.second) << "\n";
							//cout << "erasing 2\n";
							best[prev_count + 1].erase(before);
						}

						if 
						(
							(it != prev(best[prev_count + 1].end()) && is_better(*next(it), choice)) ||
							(it != best[prev_count + 1].begin() && is_better(*prev(it), choice))
						)
						{
							//cout << "erasing 3\n";
							best[prev_count + 1].erase(it);
						}
					}
				}
			}

			//cout << "best:\n";
			//for (int j = 0; j <= i + 1; j++)
			//{
			//	cout << "new_set:\n";
			//	for (pll p : best[j])
			//	{
			//		cout << p.first << " " << p.second << "\n";
			//	}
			//}
			//cout << "\n";
		}

		for (int i = 200; i >= 0; i--)
		{
			if (!best[i].empty()) return i;
		}
	}
	else if (y == 0)
	{
		vector<int> backpack(x + 1, INT_MIN);
		backpack[0] = 0;

		for (int a : A)
		{
			for (int j = x - a; j >= 0; j++)
			{
				backpack[j + a] = max(backpack[j + a], backpack[j] + 1);
			}
		}

		int maxx = 0;

		for (int i = 0; i <= x; i++)
		{
			maxx = max(maxx, backpack[i]);
		}

		return maxx;
	}

	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 24
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 14
• Subtask 6: 0 / 32