Submission #430103

#	Time	Username	Problem	Language	Result	Execution time	Memory
430103		ngrace	Jelly Flavours (IOI20_jelly)	C++14	35 / 100	2075 ms	152368 KiB

jelly

#include "jelly.h"
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;
#define v vector

int N;
v<int> A;
v<int> B;

v<v<int>> memo2;
int dp2(int cur, int left){
	if(cur==N) return 0;
	if(left==0) return 0;
	if(memo2[cur][left]!=-1) return memo2[cur][left];
	int out=dp2(cur+1,left);
	if(A[cur]<=left) out=max(out, 1+dp2(cur+1,left-A[cur]));
	return memo2[cur][left]=out;
}

v<v<v<int>>> memo3;
int dp3(int cur, int x, int y){
	if(cur==N) return 0;
	if(memo3[cur][x][y]!=-1) return memo3[cur][x][y];
	int out=dp3(cur+1,x,y);
	if(A[cur]<=x) out=max(out, 1+dp3(cur+1,x-A[cur],y));
	if(B[cur]<=y) out=max(out, 1+dp3(cur+1,x,y-B[cur]));
	return memo3[cur][x][y]=out;
}

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	N = a.size();
	bool sub4=true;
	bool sub5=true;
	for(int i=0;i<N;i++){
		A.push_back(a[i]);
		B.push_back(b[i]);
		if(a[i]!=b[i]) sub5=false;
		if(i!=0 && b[i]!=b[i-1]) sub4=false;
	}

	if(y==0){
		memo2=v<v<int>>(N,v<int>(x+1,-1));
		return dp2(0,x);
	}
	else if(sub4){
		memo2=v<v<int>>(N,v<int>(x+1,-1));
		int out=dp2(0,x);
		out+=y/b[0];
		if(out>N) out=N;
		return out;
	}
	else if(sub5){
		memo2=v<v<int>>(N,v<int>(x+y+1,-1));
		return dp2(0,x+y);
	}
	else if(N<=200 && x<=500 && y<=500){
		memo3=v<v<v<int>>>(N,v<v<int>>(x+1,v<int>(y+1,-1)));
		return dp3(0,x,y);
	}
}

Compilation message (stderr)

jelly.cpp: In function 'int find_maximum_unique(int, int, std::vector<int>, std::vector<int>)':
jelly.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

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