제출 #1199704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199704		12345678	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	174 ms	157044 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5, kx=1e4+5;

int dp[nx][kx], dpr[nx][kx], res;
vector<pair<int, int>> v;

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	int n = a.size();
	v.push_back({INT_MIN, 0});
	for (int i=0; i<n; i++) v.push_back({a[i], b[i]});
	sort(v.begin(), v.end());
	for (int i=1; i<=n; i++)
	{
		for (int j=0; j<kx; j++)
		{
			// dp[i][j]=minimum money on a given that use j on b to fill 1->i
			dp[i][j]=dp[i-1][j]+v[i].first;
			if (j>=v[i].second) dp[i][j]=min(dp[i][j], dp[i-1][j-v[i].second]);
		}
	}
	for (int i=n; i>=1; i--)
	{
		for (int j=0; j<kx; j++)
		{
			dpr[i][j]=dpr[i+1][j];
			if (j>=v[i].second) dpr[i][j]=max(dpr[i][j], dpr[i+1][j-v[i].second]+1);
		}
	}
	for (int i=0; i<=n; i++)
	{
		for (int j=0; j<=y; j++)
		{
			if (dp[i][j]<=x) res=max(res, i+dpr[i+1][y-j]);
		}
	}
	return res;
}

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