제출 #1169188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169188		miniob	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	107 ms	157000 KiB

jelly

#include <bits/stdc++.h>
using namespace std;

int minimalnykoszt2[2007][10007];
int najlepszysuf2[2007][10007];

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) 
{
	int n = a.size(), odp = 0;
	vector<pair<int, int>> nowe;
	for(int i = 0; i < n; i++)
	{
		nowe.push_back({a[i], b[i]});
	}
	sort(nowe.begin(), nowe.end());
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= x; j++)
		{
			if(nowe[i - 1].first <= j)
			{
				minimalnykoszt2[i][j] = min(minimalnykoszt2[i - 1][j] + nowe[i - 1].second, minimalnykoszt2[i - 1][j - nowe[i - 1].first]);
			}
			else
			{
				minimalnykoszt2[i][j] = minimalnykoszt2[i - 1][j] + nowe[i - 1].second;
			}
		}
		
	}
	for(int i = n; i > 0; i--)
	{
		for(int j = 0; j <= y; j++)
		{
			if(nowe[i - 1].second <= j)
			{
				najlepszysuf2[i][j] = max(najlepszysuf2[i + 1][j], najlepszysuf2[i + 1][j - nowe[i - 1].second] + 1);
			}
			else
			{
				najlepszysuf2[i][j] = najlepszysuf2[i + 1][j];
			}
		}
	}
	for(int i = 0; i <= n; i++)
	{
		if(minimalnykoszt2[i][x] <= y)
		{
			odp = max(odp, i + najlepszysuf2[i + 1][y - minimalnykoszt2[i][x]]);
		}
	}
	return odp;
}

/*int main()
{
	int n, x, y;
	cin >> n >> x >> y;
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	cout << find_maximum_unique(x, y, a, b) << endl;
	return 0;
}*/

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