Submission #1169164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169164		jbareja	Jelly Flavours (IOI20_jelly)	C++20	54 / 100	1006 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 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();

	return 0;
}

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