Submission #1169012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169012		jbareja	Jelly Flavours (IOI20_jelly)	C++20	30 / 100	973 ms	412 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 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();

	return 0;
}

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