Submission #1169029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169029		aentrenus	Jelly Flavours (IOI20_jelly)	C++20	20 / 100	1 ms	416 KiB

jelly

#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
#define all(a) a.begin(), a.end()
#define print(a) for (auto elem:a) cout<<elem<<' '; cout<<'\n'
#define segprep(b) resize(1<<((int)ceil(log2(b.size()))+1))
#define FOR(a) for (int _ = 0; _ < a; _++)

int n;

int solve1(int x, int y, vi a, vi b){
	vi for_a, for_b;
	int best = 0;
	for (int mask = 0; mask < (1<<n); mask++){
		for_a.clear();
		for_b.clear();
		for (int i = 0; i < n; i++){
			if (mask&(1<<i)){
				for_b.push_back(b.at(i));
			}
			else{
				for_a.push_back(a.at(i));
			}
		}
		// ranges::sort(for_a);
		// ranges::sort(for_b);
		sort(all(for_a));
		sort(all(for_b));
		// print(for_a);
		// print(for_b);
		int ans = 0, a_sum = 0, b_sum = 0;
		for (int i = 0; i < (int)for_a.size(); i++){
			a_sum += for_a.at(i);
			if (a_sum > x){
				ans += i;
				break;
			}
		}
		if (a_sum <= x) ans += for_a.size();
		for (int i = 0; i < (int)for_b.size(); i++){
			b_sum += for_b.at(i);
			if (b_sum > y){
				ans += i;
				break;
			}
		}
		if (b_sum <= y) ans += for_b.size();
		// cout<<"mask: "<<mask<<'\n';
		// print(for_a);
		// print(for_b);
		// cout<<"ans: "<<ans<<'\n';
		best = max(best, ans);
	}
	return best;
}

int solve3(int x, vi a, vi b){
	int sure_ans = 0;
	for (int i = n-1; i >= 0; i--){
		if (!a.at(i) || !b.at(i)){
			sure_ans++;
			a.erase(a.begin()+i);
			b.erase(b.begin()+i);
		}
	}
	sort(all(a));
	for (int i = 0; i < int(a.size()); i++){
		// cerr<<"x: "<<x<<", a[i]: "<<a.at(i)<<'\n';
		if (x >= a.at(i)){
			x -= a.at(i);
			continue;
		}
		return i+sure_ans;
	}
	return (int)a.size()+sure_ans;
}

int find_maximum_unique(int x, int y, vi a, vi b) {
	n = a.size();

	if (n <= 12) return solve1(x, y, a, b);
	if (y == 0) return solve3(x, a, b);
	return 0;
}

// static int x, y;
// static std::vector<int> a, b;

// int main() {
//     assert(scanf("%d %d %d", &n, &x, &y) == 3);
//     a.resize(n);
//     b.resize(n);
//     for (int i = 0; i < n; i++) {
//         assert(scanf("%d %d", &a[i], &b[i]) == 2);
//     }

//     fclose(stdin);

//     // bool same = solve1(x, y, a, b) == solve3(x, a);
// 	int brut = solve1(x, y, a, b);
// 	int trzy = solve3(x, a, b);
// 	bool same = brut == trzy;

//     // printf("%d\n", answer);
// 	if (same){
// 		printf("OK\n");
// 	}
// 	else{
// 		printf("ZLE\n");
// 		printf("Odp bruta: %d, odp trzy: %d\n", brut, trzy);
// 	}
// }

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