Submission #986147

#	Time	Username	Problem	Language	Result	Execution time	Memory
986147		Sofiatpc	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	70 ms	157268 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define sc second
const int MAXN = 2005, MAX = 1e4+5;
int dp[MAXN][MAX], dp2[MAXN][MAX];
vector< pair<int,int> >v;
 
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int n = a.size();

	for(int i = 0; i < n; i++)v.push_back({a[i],b[i]});
	sort(v.begin(),v.end());

	for(int j = 1; j <= n; j++)
		for(int k = 0; k <= x; k++){
			if(k < v[j-1].fi)dp[j][k] = dp[j-1][k]+v[j-1].sc;
			else dp[j][k] = min(dp[j-1][k]+v[j-1].sc, dp[j-1][k-v[j-1].fi]);
		}

	for(int j = n; j >= 1; j--)
		for(int k = 0; k <= y; k++){
			if(k < v[j-1].sc)dp2[j][k] = dp2[j+1][k];
			else dp2[j][k] = max(dp2[j+1][k], dp2[j+1][k-v[j-1].sc]+1);
		}

	int ans = 0; 
	for(int i = 0; i <= n; i++){
		if(y < dp[i][x])continue;
		int r = y - dp[i][x];
		ans = max(i+dp2[i+1][r], ans);
	}
	return ans;
}

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