제출 #1169201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169201		Piokemon	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	66 ms	78660 KiB

jelly

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

constexpr int N = 2000;
constexpr int A = 10'000;

int dp[N+9][A+9];
bool mam[N+9];

int find_maximum_unique(int sA, int sB, vector<int> a, vector<int> b) {
	int n = a.size();
	vector<pair<int,int>> sa,sb;
	for (int x=0;x<n;x++){
		sa.push_back({a[x],x});
		sb.push_back({b[x],x});
	}
	sort(sa.begin(),sa.end()); sort(sb.begin(),sb.end());
	for (int x=0;x<=A;x++)dp[0][x]=1e9;
	dp[0][0]=b[sa[0].second]; dp[0][sa[0].first]=0;
	int odp=0;
	mam[sa[0].second]=1;
	for (int x=1;x<n;x++){
		int zost=-1;
		for (int y=0;y<=sA;y++)zost=max(zost,sB-dp[x-1][y]);
		if (zost<0)break;
		//cerr << x << ' ' << zost << '\n';
		int temp=x;
		for (int y=0;y<n;y++){
			if (!mam[sb[y].second]){
				if (zost >= sb[y].first){
					zost-=sb[y].first;
					temp++;
				}
				else break;
			}
		}
		odp = max(odp,temp);

		mam[sa[x].second]=1;
		for (int y=0;y<=A;y++){
			dp[x][y] = dp[x-1][y]+b[sa[x].second];
			if (y>=sa[x].first)dp[x][y]=min(dp[x][y],dp[x-1][y-sa[x].first]);
		}
	}
	int tempie=0;
	for (int x:a)tempie+=x;
	if (tempie<=sA)return n;
	return odp;
}

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