Submission #318659

#	Time	Username	Problem	Language	Result	Execution time	Memory
318659		SnowFlake7	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	176 ms	78696 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
#define NMAX 2005
#define INF 2000000000

using namespace std;

struct jelly {
	int a,b;
};
jelly v[NMAX];
int dp[NMAX][10005],cost[NMAX];

bool cmp1(jelly a, jelly b) {
	return a.a < b.a;
}
bool cmp2(jelly a, jelly b) {
	return a.b < b.b;
}
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int ind,ans = 0,n = a.size(),rest;
	for (int i = 1;i <= n;i++)
		v[i] = {a[i - 1], b[i - 1]};
	sort(v + 1, v + n + 1, cmp1);
	for (int i = 0;i <= n;i++) {
		for(int j = 0;j <= y;j++)
			dp[i][j] = INF;
	}
	dp[0][0] = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= y;j++) {
			if (dp[i - 1][j] == INF)
				continue;
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + v[i].a);
			if(j + v[i].b <= y)
				dp[i][j + v[i].b] = min(dp[i][j + v[i].b], dp[i - 1][j]);
		}
	}
	cost[0] = 0;
	for (int i = 1;i <= n;i++) {
		cost[i] = INF;
		for (int j = 0;j <= y;j++) {
			if (dp[i][j] <= x) {
				cost[i] = j;
				break;
			}
		}
	}
	for (int i = n;i >= 0;i--) {
		if (cost[i] == INF)
			continue;
		rest = y - cost[i];
		if (i < n)
			sort(v + i + 1, v + n + 1,cmp2);
		ind = i + 1;
		while (ind <= n && rest >= 0) {
			rest -= v[ind].b;
			ind++;
		}
		if(ind == n + 1 && rest >= 0)
			ans = n;
		else
			ans = max(ans, ind - 2);
	}
	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