Submission #433430

#	Time	Username	Problem	Language	Result	Execution time	Memory
433430		Pbezz	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	178 ms	152516 KiB

jelly

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

using namespace std;

#define ll long long
#define pb push_back
typedef pair<int,int> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

int find_maximum_unique(int x,int y,std::vector<int>a,std::vector<int>b){
	int n = a.size(),i,j;

	pii c[n];

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

	sort(c,c+n);

	int adp[n+1][x+1]={},bdp[n+1][y+1]={};
//adp[i][j] e minimo dinheiro de b para comprar i primeiros de c
//com budget de j na loja A


	for(i=1;i<=n;i++){
	for(j=0;j<=x;j++){

	adp[i][j] = adp[i-1][j] + c[i-1].second;

	if(j-c[i-1].first>=0){
	adp[i][j] = min(adp[i][j], adp[i-1][j-c[i-1].first] );}
//	cout<<j<<" "<<adp[i][j]<<"  ";
	}
}

	for(i=n-1;i>=0;i--){
	for(j=0;j<=y;j++){

	bdp[i][j] = bdp[i+1][j];

	if(j-c[i].second>=0){
	bdp[i][j]=max(bdp[i][j], 1 + bdp[i+1][j-c[i].second]);
	}

	}
}
int ans=0;
	for(i=0;i<=n;i++){

	if(y-adp[i][x]>=0){
ans=max(ans,i+bdp[i][y-adp[i][x]]);
//	cout<<i<<" "<<adp[i][x]<<" "<<bdp[i][y-adp[i][x]]<<endl;
}
}

	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