Submission #1242835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242835		hiikunZ	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	133 ms	154996 KiB

jelly

#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int find_maximum_unique(int X, int Y, std::vector<int> A, std::vector<int> B) {
	ll MAX = 1e18;
	int N = A.size();
	vector<tuple<ll,ll>> S;
	for(ll i = 0;i < N;i++) S.emplace_back(A[i],B[i]);
	sort(S.begin(),S.end());
	for(ll i = 0;i < N;i++) tie(A[i],B[i]) = S[i];
	// ABBBAABABXXBXBX
	vector<vector<ll>> AB_DP(N + 1,vector<ll>(X + 1,MAX));
	//AB_DP[0][0] = 0;
	for(ll i = 0;i <= X;i++) AB_DP[0][i] = 0;
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j <= X;j++) if(AB_DP[i][j] != MAX){
			// A
			if(j + A[i] <= X) AB_DP[i + 1][j + A[i]] = min(AB_DP[i + 1][j + A[i]],AB_DP[i][j]);
			// B
			AB_DP[i + 1][j] = min(AB_DP[i + 1][j],AB_DP[i][j] + B[i]);
		}
	}
	vector<ll> B_DP(N + 1,MAX);
	B_DP[0] = 0;
	ll ans = 0;
	for(ll i = N - 1;i >= 0;i--){
		for(ll j = 0;j <= N;j++) if(AB_DP[i + 1][X] + B_DP[j] <= Y) ans = max(ans,i + 1 + j);
		for(ll j = N - 1;j >= 0;j--) B_DP[j + 1] = min(B_DP[j + 1],B_DP[j] + B[i]);
		for(ll j = 0;j <= N;j++) if(AB_DP[i][X] + B_DP[j] <= Y) ans = max(ans,i + j);
	}
	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