Submission #1213002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213002		ChuanChen	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	129 ms	157000 KiB

jelly

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

typedef pair<int, int> pii;
const int MAXN = 2e3+5, MAXY = 1e4+5, INF = 2e9;

int dp1[MAXN][MAXY];//dp1[i][x] := min y gasto pegando todos prefix i e usando até x.
int dp2[MAXN][MAXY];//dp2[i][y] :+ #max que pego do B de sufixo[i..n] gastando ate Y.

int find_maximum_unique(int X, int Y, std::vector<int> a, std::vector<int> b) {
	int n = a.size();
	vector<pii> tmp;
	for(int i = 0; i < n; i++)
		tmp.emplace_back(a[i], b[i]);
	sort(tmp.begin(), tmp.end());
	for(int i = 0; i < n; i++){
		a[i] = tmp[i].first;
		b[i] = tmp[i].second;
		// cout << a[i] << ' ' << b[i] << '\n';
	}

	for(int i = n-1; i >= 0; i--){
		for(int y = 0; y <= Y; y++){
			if(i == n) dp2[i][y] = (b[i]<=y)? 1:0;
			dp2[i][y] = max(dp2[i+1][y], (b[i]<=y)? dp2[i+1][y-b[i]]+1:0);
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int x = 0; x <= X; x++){
			if(!i) dp1[i][x] = min(b[i], (a[i]<=x)? 0:INF);
			else dp1[i][x] = min(dp1[i-1][x]+b[i],(a[i]<=x)? dp1[i-1][x-a[i]]:INF);
		}
		// cout << "Gastei Y = " << dp1[i][X] << " para pegar " << 1+i << " primeiras\n";
		if(dp1[i][X] > Y) break;
		if(i == n-1) ans = n;
		// cout << "Sobrando " << Y-dp1[i][X] << " para sufix " << i+1 << ", ainda pego " << dp2[i+1][Y-dp1[i][X]] << '\n';
		ans = max(ans, 1+i+dp2[i+1][Y-dp1[i][X]]);
		// cout << "ans = " << ans << "\n\n";
	}

	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