제출 #1169215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169215		jbareja	Jelly Flavours (IOI20_jelly)	C++20	68 / 100	998 ms	191820 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>

using namespace std;

int n; // liczba produktów w każdym ze sklepów

int x; // pieniądze do wydania w sklepie A
int y; // pieniądze do wydania w sklepie B

vector<int> a; // ceny produktów w sklepie A
vector<int> b; // ceny produktów w sklepie B

int calc_res(int m) {
	int sum_x = 0, sum_y = 0, cnt_diff = 0;
	for (int i=0; i<n; i++) {
		bool temp = false;
		if (m & (1 << i)) {
			sum_x += a[i];
			temp = true;
		}
		if (m & (1 << (i+n))) {
			sum_y += b[i];
			temp = true;
		}
		if (temp) cnt_diff++;
	}
	if (sum_x > x || sum_y > y) return 0;
	return cnt_diff;
}

int brute_exp() {
	int max_res = 0;
	for (int i=0; i<(1<<(2*n)); i++) {
		max_res = max(max_res, calc_res(i));
	}
	return max_res;
}

int dp_n_to_power_of_3() {
	vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(x+1, vector<int>(y+1, 0)));
	int max_res = 0;
	for (int i=1; i<=n; i++) {
		for (int X=0; X<=x; X++) {
			for (int Y=0; Y<=y; Y++) {
				dp[i][X][Y] = dp[i-1][X][Y];
				int ai = a[i-1], bi = b[i-1];
				if (X >= ai) dp[i][X][Y] = max(dp[i][X][Y], dp[i-1][X-ai][Y]+1);
				if (Y >= bi) dp[i][X][Y] = max(dp[i][X][Y], dp[i-1][X][Y-bi]+1);
				max_res = max(max_res, dp[i][X][Y]);
			}
		}
	}
	return max_res;
}

int brute_y_equals_to_0() {
	priority_queue<int> Q; // < -a[i] >
	int res = 0;
	for (int i=0; i<n; i++) {
		if (b[i] == 0) {
			res++;
			continue;
		}
		Q.push(-a[i]);
	}
	int budget = x;
	while (!Q.empty()) {
		int ai = -Q.top(); Q.pop();
		if (budget - ai >= 0) {
			budget -= ai;
			res++;
		}
		else break;
	}
	return res;
}

int heura_bi_equalst_to_bj() {
	priority_queue<int> Q; // < -a[i] >
	for (int i=0; i<n; i++) Q.push(-a[i]);
	int res = 0;
	int budget = x;
	while (!Q.empty()) {
		int ai = -Q.top(); Q.pop();
		if (budget - ai >= 0) {
			budget -= ai;
			res++;
		}
		else break;
	}
	int max_bought_in_b = (b[0] != 0) ? y / b[0] : n;
	return min(n, res + max_bought_in_b);
}

int heura_ai_equals_to_bi() {
	if (y > x) {
		swap(x, y);
		swap(a, b);
	}
	priority_queue<int> Q;
	for (int i=0; i<n; i++) Q.push(-a[i]);
	int budget = x;
	vector<int> chosen;
	multiset<int> chosen_X;
	multiset<int> chosen_Y;
	int sum_of_chosen = 0;
	while (!Q.empty()) {
		int ai = -Q.top(); Q.pop();
		if (budget - ai >= 0) {
			budget -= ai;
			chosen.push_back(ai);
			chosen_X.insert(ai);
			sum_of_chosen += ai;
		}
		else {
			Q.push(-ai);
			break;
		}
	}
	int rest_x = budget;
	budget = y;
	while (!Q.empty()) {
		int ai = -Q.top(); Q.pop();
		if (budget - ai >= 0) {
			budget -= ai;
			chosen.push_back(ai);
			chosen_Y.insert(ai);
			sum_of_chosen += ai;
		}
		else {
			Q.push(-ai);
			break;
		}
	}
	int rest_y = budget;
	int rest = rest_x + rest_y;
	if (Q.empty() || -Q.top() > rest || rest_x == 0 || rest_y == 0) return ssize(chosen);
	int candidate = -Q.top();

	// cout << "rest_x = " << rest_x << ", rest_y = " << rest_y << endl;
	// cout << "candidate = " << candidate << endl;

	auto it = chosen_X.lower_bound(candidate - rest_x);
	// cout << "do wywalenia z X: " << *it << endl;
	if (it != chosen_X.end() && *it <= rest_y) return ssize(chosen) + 1;

	it = chosen_Y.lower_bound(candidate - rest_y);
	// cout << "do wywalenia z Y: " << *it << endl;
	if (it != chosen_Y.end() && *it <= rest_x) return ssize(chosen) + 1;

	return -1;
}

int find_maximum_unique(int _x, int _y, std::vector<int> _a, std::vector<int> _b) {
	n = _a.size(); x = _x; y = _y; a = _a; b = _b;

	if (x <= 500 && y <= 500 && n <= 12) return brute_exp();
	if (y == 0) return brute_y_equals_to_0();

	bool bi_equals_to_bj = true;
	bool ai_equals_to_bi = true;

	int bj = b[0];
	for (int i=0; i<n; i++) {
		if (b[i] != bj) {
			bi_equals_to_bj = false;
			if (!ai_equals_to_bi) break;
		}
		if (a[i] != b[i]) {
			ai_equals_to_bi = false;
			if (!bi_equals_to_bj) break;
		}
	}

	if (bi_equals_to_bj) return heura_bi_equalst_to_bj();
	if (x <= 500 && y <= 500 && n <= 200) return dp_n_to_power_of_3();
	if (ai_equals_to_bi) return heura_ai_equals_to_bi();

	return 0;
}

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