Submission #886528

#TimeUsernameProblemLanguageResultExecution timeMemory
886528vjudge1Gym Badges (NOI22_gymbadges)C++17
15 / 100
2082 ms189728 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...