Submission #300184

#	Time	Username	Problem	Language	Result	Execution time	Memory
300184		model_code	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	179 ms	157024 KiB

jelly

// gug-full
#include "jelly.h"
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<60;
const double eps = 1e-4;
const double PI=3.1415926535897932;

int fdp[2009][10009],bdp[2009][10009];//(i,a used)->min b,(i,b used)->max value
PII c[2009];
int n;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){
	n = a.size();
	for (int i = 0; i < n; i++) c[i] = make_pair(a[i], b[i]);
	sort(c,c+n);
	REPP(i,1,n+1){
		REP(j,x+1){
			fdp[i][j]=fdp[i-1][j]+c[i-1].S;
			if(j>=c[i-1].F){
				fdp[i][j]=min(fdp[i][j],fdp[i-1][j-c[i-1].F]);
			}
		}
	}
	for(int i=n-1;i>=0;i--){
		REP(j,y+1){
			bdp[i][j]=bdp[i+1][j];
			if(j>=c[i].S){
				bdp[i][j]=max(bdp[i][j],bdp[i+1][j-c[i].S]+1);
			}
		}
	}
	int ans=0;
	REP(i,n+1){
		int yleft=y-fdp[i][x];
		if(yleft>=0)ans=max(ans,i+bdp[i][yleft]);
	}
	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