Submission #426557

#	Time	Username	Problem	Language	Result	Execution time	Memory
426557		Apiram	Jelly Flavours (IOI20_jelly)	C++14	24 / 100	1020 ms	2097156 KiB

jelly

#include "jelly.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int find_maximum_unique(int x, int y, std::vector<int> arr, std::vector<int> brr) {
	int n = arr.size();
	bool ok=true;
	bool okay=true;
	int sum1=0;
	for (int i =0;i<n;++i){
		if (arr[i]!=brr[i]){
			ok=false;
		}
		if (i>0){
			if (brr[i]!=brr[i-1])okay=false;
		}
		sum1+=arr[i];
	}
	if (okay){
		vector<pair<int,int>>crr(n);
		for (int i=0;i<n;++i){
			crr[i]={arr[i],brr[i]};
		}
		sort(crr.begin(),crr.end());
		int ans=0;
		n--;
		while(n>=0){
			if (y-crr[n].second>=0){
				y-=crr[n].second;
				--n;
				ans++;
			}
			else break;
		}
		for (int i =0;i<=n;++i){
			if (x-crr[i].first<0)break;
			x-=crr[i].first;
			ans++;
		}
		return ans;
	}
	if (!ok){
	int dp2[n][sum1+1];
	memset(dp2,0,sizeof dp2);
	for (int i =0;i<n;++i){
	dp2[i][0]=1;
	for (int j =0;j<=sum1;++j){
	    if (dp2[i][j]==1){
	    	dp2[i+1][j+arr[i]]=1;
	    }
	    dp2[i+1][j]=max(dp2[i][j],dp2[i+1][j]);
	}
}

vector<int>ans;
ans.push_back(0);
for (int i = 1;i<x;++i){
if (dp2[n][i]==1)ans.push_back(i);
}
ans.push_back(x);

	int dp [n+1][ans.size()][y+1];
	memset(dp,0,sizeof dp);
	for (int i =1;i<=n;++i){
		for (int j =0;j<ans.size();++j){
			for (int k =0;k<=y;++k){
				dp[i][j][k] = max({(ans[j]-arr[i-1]>=0)?dp[i-1][find(ans.begin(),ans.end(),ans[j]-arr[i-1])-ans.begin()][k]+1:0,(k-brr[i-1]>=0)?dp[i-1][j][k-brr[i-1]]+1:0,dp[i-1][j][k],dp[i][j][k]});
			}
		}
	}
	return dp[n][ans.size()-1][y];}
	else {
		int dp1[n+1][x+y+1];
		memset(dp1,0,sizeof dp1);
		for (int i =1;i<=n;++i){
			for (int j =0;j<=x+y;++j){
			dp1[i][j] = max({(j-arr[i-1]>=0)?dp1[i-1][j-arr[i-1]]+1:0,dp1[i][j],dp1[i-1][j]});
		}
	}
	return dp1[n][x+y];
}
}

Compilation message (stderr)

jelly.cpp: In function 'int find_maximum_unique(int, int, std::vector<int>, std::vector<int>)':
jelly.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int j =0;j<ans.size();++j){
      |                 ~^~~~~~~~~~~

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