Submission #317919

#	Time	Username	Problem	Language	Result	Execution time	Memory
317919		ivan_tudor	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	172 ms	78900 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
struct jelly{
	int a, b;
};
const int N = 2005;
const int INF = INT_MAX;
jelly v[N];
bool cmpj(jelly a, jelly b){
	return a.a < b.a;
}
bool cmpb(jelly a, jelly b){
	return a.b < b.b;
}
int dp[N][10005];
int cost[N];
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int n = a.size();
	for(int i=1;i<=n;i++){
		v[i] = {a[i-1], b[i-1]};
	}
	sort(v+ 1, v+n+1, cmpj);
	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;
			}
		}
	}
	int ans = 0;
	for(int i= n ;i>=0;i--){
		if(cost[i] == INF)
			continue;
		int ramas =  y - cost[i];
		if(i < n)
			sort(v+i+1,v+n+1,cmpb);
		int j = i + 1;
		while(j <= n && ramas >= 0){
			ramas -= v[j].b;
			j++;
		}
		if(j == n+1 && ramas >=0)
			ans = n;
		else
			ans = max(ans, i + j - i - 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