Submission #1025502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025502		TheWilp	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	73 ms	856 KiB

jelly

#include "jelly.h"
#include <vector>
#include <algorithm>
#include <map>

const int MAXMONEY = 10005;

class name{
public:
	int x;
	int y;
	bool operator<(const name& other) const{
		return x < other.x;
	}
};

class node{
public:
	int value;
	int count;
	node* left = nullptr;
	node* right = nullptr;
};

int get_mid(int left,int right) {
	return (right - left) / 2 + left;
}

int get_value(node* root) {
	if(!root) return 0;
	return root->value;
}

int get_count(node* root) {
	if(!root) return 0;
	return root->count;
}

void add(node* root,int pos,int value,int left = 0,int right = MAXMONEY) {
	if(right == left) {
		root->value = value;
		root->count = 1;
		return;
	}
	int mid = get_mid(left,right);
	if(pos <= mid) {
		if(root->left == nullptr) root->left = new node();
		add(root->left,pos,value,left,mid);
	}
	else {
		if(root->right == nullptr) root->right = new node();
		add(root->right,pos,value,mid + 1,right);
	}
	root->value = get_value(root->left) + get_value(root->right);
	root->count = get_count(root->left) + get_count(root->right);
}

int get_max_count(node* root,int max_value,int left = 0,int right = MAXMONEY) {
	if(!root) return 0;
	int mid = get_mid(left,right);
	if(max_value >= get_value(root->left)) {
		return get_count(root->left) + get_max_count(root->right,max_value - get_value(root->left),mid + 1,right);
	}
	else {
		return get_max_count(root->left,max_value,left,mid);
	}
}

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	int N = a.size();
	int ans = 0;
	std::vector<name> v(N);
	for(int q = 0;q < N;q++) {
		v[q].x = a[q];
		v[q].y = b[q];
	}
	std::sort(v.begin(),v.end());
	std::vector<int> dp(MAXMONEY,20000);
	dp[0] = 0;
	std::vector<int> res(N,20000);
	int min_require = 0;
	for(int q = 0;q < N;q++) {
		min_require += v[q].x;
		for(int w = MAXMONEY - 1;w>=0;w--) {
			if(w < v[q].x) break;
			dp[w] = std::min(dp[w],dp[w - v[q].x] + v[q].y);
		}
		for(int w = std::max(0,min_require - x);w < MAXMONEY;w++) {
			if(dp[w] <= y) {
				res[q] = std::min(res[q],dp[w]);
			}
		}
	}
	if(res.back() <= y) return N;

	std::vector<name> u(N);
	for(int q = 0;q < N;q++) {
		u[q].x = v[q].y;
		u[q].y = q;
	}
	std::sort(u.begin(),u.end());
	std::map<int,int> mm;
	for(int q = 0;q < N;q++) {
		mm[u[q].y] = q;
	}
	
	node* root = new node();
	for(int q = N - 1;q>=1;q--) {
		add(root,mm[q],v[q].y);
		if(res[q - 1] <= y) {
			int remain_value = y - res[q - 1];
			ans = std::max(ans,q + get_max_count(root,remain_value));
		}
	}
	add(root,mm[0],v[0].y);
	ans = std::max(ans,get_max_count(root,y));

	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