Submission #748572

#	Time	Username	Problem	Language	Result	Execution time	Memory
748572		Sharky	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	313 ms	152916 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1E9;

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	int n = a.size();
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) v.emplace_back(a[i], b[i]);
	sort(v.begin(), v.end(), [] (pair<int, int> lhs, pair<int, int> rhs) {
		if (lhs.first == rhs.first) return lhs.second < rhs.second;
		return lhs.first < rhs.first;
	});
	for (int i = 0; i < n; i++) a[i] = v[i].first, b[i] = v[i].second;
	vector<vector<int>> dp1(n + 2, vector<int> (x + 1, INF));
	dp1[1][0] = 0;
	for (int i = 2; i <= n + 1; i++) {
		for (int j = 0; j <= x; j++) {
			if (j >= a[i-2]) dp1[i][j] = min(dp1[i][j], dp1[i-1][j - a[i-2]]);
			dp1[i][j] = min(dp1[i][j], dp1[i-1][j] + b[i-2]);
		}
	}
	vector<vector<int>> dp2(n + 2, vector<int> (y + 1, -INF));
	dp2[n + 1][0] = 0;
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= y; j++) {
			if (j >= b[i-1]) dp2[i][j] = max(dp2[i][j], dp2[i+1][j - b[i-1]] + 1);
			dp2[i][j] = max(dp2[i][j], dp2[i+1][j]);
		}
	}
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= y; j++) dp2[i][j] = max(dp2[i][j], dp2[i][j-1]);
	}
	int ans = 0;
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 0; j <= x; j++) {
			int cur = i - 1;
			if (y >= dp1[i][j]) cur += dp2[i][y - dp1[i][j]];
			if (y >= dp1[i][j]) {
				// cout << i-1 << ' ' << dp2[i][y - dp1[i][j]] << '\n';
				ans = max(ans, cur);
			}
		}
	}
	return ans;
}

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