Submission #559473

#	Time	Username	Problem	Language	Result	Execution time	Memory
559473		AlperenT	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	234 ms	157260 KiB

jelly

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

const int INF = 1e9 + 5;

using namespace std;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){
	int n = a.size(), ans = 0;

	vector arr(n, pair{0, 0});

	for(int i = 0; i < n; i++) arr[i] = {a[i], b[i]};

	sort(arr.begin(), arr.end());

	vector dp1(n, vector(10000 + 5, INF));
	vector dp2(n, vector(10000 + 5, 0));

	dp1[0][0] = arr[0].second;
	dp1[0][arr[0].first] = 0;

	for(int i = 1; i < n; i++){
		for(int j = 0; j <= x; j++){
			dp1[i][j] = dp1[i - 1][j] + arr[i].second;
			if(j >= arr[i].first) dp1[i][j] = min(dp1[i][j], dp1[i - 1][j - arr[i].first]);
		}
	}

	dp2[n - 1][arr[n - 1].second] = 1;

	for(int i = n - 2; i >= 0; i--){
		for(int j = 0; j <= y; j++){
			dp2[i][j] = dp2[i + 1][j];
			if(j - arr[i].second >= 0) dp2[i][j] = max(dp2[i][j], dp2[i + 1][j - arr[i].second] + 1);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 1; j <= y; j++){
			dp2[i][j] = max(dp2[i][j], dp2[i][j - 1]);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= x; j++){
			if(dp1[i][j] <= y){
				ans = max(ans, (i + 1) + (i + 1 < n ? dp2[i + 1][y - dp1[i][j]] : 0));
			}
		}
	}

	for(int i = 0; i <= y; i++) ans = max(ans, dp2[0][i]);

	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