Submission #1318001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318001		nagorn_ph	Jelly Flavours (IOI20_jelly)	C++20	0 / 100	1 ms	332 KiB

jelly

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

using namespace std;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int n = a.size();
	reverse(a.begin(), a.end()); a.emplace_back(0); reverse(a.begin(), a.end());
	reverse(b.begin(), b.end()); b.emplace_back(0); reverse(b.begin(), b.end());
	vector <pair <int, int>> v;
	for (int i = 1; i <= n; i++) {
		v.emplace_back(a[i], b[i]);
	}
	sort(v.begin(), v.end());
	if (x > y) swap(x, y);
	vector <pair <int, int>> dp(x + 1);
	for (int i = 0; i < n; i++) {
		auto [aa, bb] = v[i];
		for (int j = aa; j <= x; j++) {
			dp[j] = max(dp[j], {dp[j - aa].first + 1, i});
		}
	}
	pair <int, int> mx = {0, 0};
	for (int i = 0; i <= x; i++) {
		mx = max(mx, {dp[i].first, i});
	}
	int cur = dp[mx.second].second;
	int xx = mx.first;
	vector <bool> visited(n + 1);
	while (!visited[cur]) {
		visited[cur] = true;
		cur = dp[xx - v[cur].first].second;
		xx -= v[cur].first;
	}
	int ans = count(visited.begin(), visited.end(), true);
	for (int i = 0; i < n; i++) {
		if (visited[i]) continue;
		if (y >= v[i].first) ans++, y -= v[i].first;
	}
	return ans;
}

/*
sub 1-2 , 3: constraints , y = 0
dp[i][j][k] = max ans when we used i at a, j at b, checked up to k
answer is at dp[x][y][n]

sub 4: b is all equal
greedy stupid again

sub 5: a and b are same

*/

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