Submission #1169103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169103		owieczka	Jelly Flavours (IOI20_jelly)	C++20	68 / 100	118 ms	2588 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
int dp[2][550][550];
bool backpack[11'000];

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	//
	int n = a.size();
	if (!y)
	{
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			if (b[i] == 0)
			{
				ans++;
				a[i] = INT_MAX;
			}
		}
		sort(a.begin(), a.end());
		for (int i = 0; i < n; i++)
		{
			// cerr << a[i] << ' ';
			if (x < a[i])break;
			ans++;
			x -= a[i];
		}
		return ans;
	}
	bool podz5 = 1;
	for (int i = 0; i < n; i++)
	{
		if (a[i] != b[i])podz5=0;
	}
	if (podz5)
	{
		int ans = 0;
		sort(a.begin(), a.end());
		int s = 0;
		backpack[0] = 1;
		for (int i = 0; i < n; i++)
		{
			s += a[i];
			for (int k = x; k >= a[i]; k--)
			{
				if(backpack[k - a[i]])backpack[k]=1;
			}
			int as = 0;
			for (int k = x; k >= 0; k--)
			{
				if (backpack[k])
				{
					as = k;
					break;
				}
			}
			if (s - as <= y)ans = i + 1;
		}
		return ans;
	}
	else if (x <= 500 && y <= 500 && n <= 200)
	{

		for (int k = 0; k < n; k++)
		{
			int t = k % 2;
			for (int i = 0; i <= x; i++)
			{
				for (int j = 0; j <= y; j++)
				{
					dp[t][i][j] = dp[!t][i][j];
				}
			}
			for (int i = 0; i <= x; i++)
			{
				for (int j = 0; j <= y; j++)
				{
					if (i >= a[k])
					{
						dp[t][i][j] = max(dp[t][i][j], dp[!t][i - a[k]][j] + 1);
					}
					if (j >= b[k])
					{
						dp[t][i][j] = max(dp[t][i][j], dp[!t][i][j - b[k]] + 1);
					}
				}
			}
		}
		int m = 0;
		for (int i = 0; i <= x; i++)
		{
			for (int j = 0; j <= y; j++)
			{
				m = max(m, dp[0][i][j]);
				m = max(m, dp[1][i][j]);
			}
		}
		return m;
	}
	else 
	{
		sort(a.begin(), a.end());
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			if (x < a[i])break;
			ans++;
			x -= a[i];
		}
		while (y >= b[0])
		{
			y -= b[0];
			ans++;
		}
		return min(ans, n);
	}
}

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