Submission #318657

#	Time	Username	Problem	Language	Result	Execution time	Memory
318657		SnowFlake7	Jelly Flavours (IOI20_jelly)	C++14	0 / 100	30 ms	18796 KiB

jelly

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

using namespace std;

struct jelly {
	int a, b;
}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,rest,n = a.size();
	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, rest - 2);
	}
	return ans;
}

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