Submission #433264

#	Time	Username	Problem	Language	Result	Execution time	Memory
433264		amunduzbaev	Jelly Flavours (IOI20_jelly)	C++14	24 / 100	233 ms	156832 KiB

jelly

#include "jelly.h"

#ifndef EVAL
#include "grader.cpp"
#endif

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

const int N = 2005;
int dp[N][(int)1e4+5];
int rdp[N][(int)1e4+5];

#define ff first
#define ss second
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int mod = 1e9+7;
	
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int n = (int)a.size();
	vector<pair<int, int>> tt;
	for(int i=0;i<n;i++) tt.push_back({a[i], b[i]});
	tt.push_back({-1, -1});
	sort(tt.begin(), tt.end());
	
	memset(dp, 127, sizeof dp);
	memset(dp[0], 0, sizeof dp[0]);
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=x;j++){
			if(~dp[i-1][j]) umin(dp[i][j], dp[i-1][j] + tt[i].ss);
			if(j >= tt[i].ff && ~dp[i-1][j-tt[i].ff]) umin(dp[i][j], dp[i-1][j - tt[i].ff]);
		}
	}
	
	for(int i=n;i>0;i--){
		for(int j=0;j<=y;j++){
			if(j) umax(rdp[i][j], rdp[i][j-1]);
			if(j >= tt[i].ss) umax(rdp[i][j], rdp[i+1][j-tt[i].ss] + 1);
		}
	}
	
	int res = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=x;j++){
			if(dp[i][j] <= y) umax(res, i + rdp[i+1][y - dp[i][j]]);
		}
	}
	
	//~ for(int j=0;j<=x;j++){
		//~ for(int i=1;i<=n;i++) cout<<dp[i][j]<<" ";
		//~ cout<<"\n";
	//~ } cout<<"\n";
	
	//~ for(int j=0;j<=y;j++){
		//~ for(int i=1;i<=n;i++) cout<<rdp[i][j]<<" ";
		//~ cout<<"\n";
	//~ } cout<<"\n";
	
	return res;
}

/*

	5 6 12
	5 1 5 6 3 
	3 5 4 6 7

*/

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