Submission #757967

#TimeUsernameProblemLanguageResultExecution timeMemory
757967jer033Gym Badges (NOI22_gymbadges)C++17
24 / 100
218 ms4380 KiB
#include <algorithm>
#include <iostream>

long long xis[500005];
long long lis[500005];
int permu[11];
using namespace std;

int main()
{
	int n;
	cin >> n;
	if (n<=10)
	{
		for (int i=1; i<=n; i++)
		{
			cin >> xis[i];
		}
		for (int i=1; i<=n; i++)
		{
			cin >> lis[i];
		}
		//code the brute force
		int nfactorial=1;
		for (int i=2; i<=n; i++)
			nfactorial*=i;
		for (int i=1; i<=n; i++)
			permu[i]=i;
		int maxbadges=0;
		for (int i=1; i<=nfactorial; i++)
		{
			//check how far it goes
			int badgec=1;
			long long level=xis[permu[1]];
			while (badgec<n and level<=lis[permu[badgec+1]])
			{
				level+=xis[permu[badgec+1]];
				badgec++;
			}
			maxbadges=max(maxbadges, badgec);
			//code the next permutation
			int swapa=n-1;
			while (permu[swapa]>permu[swapa+1])
				swapa--;
			int swapb=swapa+1;
			for (int j=swapa+2; j<=n; j++)
			{
				if (permu[j]>permu[swapa])
					swapb=j;
			}
			int x=permu[swapa];
			permu[swapa]=permu[swapb];
			permu[swapb]=x;
			sort(permu+swapa+1, permu+n+1);
		}
		cout << maxbadges << '\n';
	}
	else
	{
		for (int i=0; i<n; i++)
		{
			cin >> xis[i];
		}
		sort(xis, xis+n);
		long long li;
		cin >> li;
		int badge=0;
		long long level=0;
		while (level<=li)
		{
			level+=xis[badge];
			badge++;
		}
		cout << badge << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...