Submission #886528

#	Time	Username	Problem	Language	Result	Execution time	Memory
886528		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	15 / 100	2082 ms	189728 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1ll<<((int)(bi)))
int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> arr(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i].second;
	}
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i].first;
	}
	if (n>5000){
		cout<<"NO"<<endl;
		return 0;
	}
	sort(arr.begin(), arr.end(), [&](pair<int,int> a, pair<int,int> b){
		return (a.first+a.second)<(b.first+b.second);
	});
	map<int,int> dp[n];
	function<int(int,int)> f = [&](int node, int val)->int{
		if (node>=n) return 0;
		if (dp[node].count(val)) return dp[node][val];
		if (arr[node].first<val){
			return dp[node][val]=f(node+1,val);
		}
		return dp[node][val]=max(f(node+1,val+arr[node].second)+1,f(node+1,val));
	};
	cout<<f(0,0)<<endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 9
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49