Submission #1212998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212998		ChuanChen	Jelly Flavours (IOI20_jelly)	C++20	0 / 100	101 ms	156488 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;
	}

	for(int i = n; 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);
		}
		if(dp1[i][X] > Y) break;
		if(i == n) ans = i;
		ans = max(ans, i+dp2[i+1][Y-dp1[i][X]]);
	}

	return ans;
}

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