Submission #757965

#	Time	Username	Problem	Language	Result	Execution time	Memory
757965		jer033	Gym Badges (NOI22_gymbadges)	C++17	15 / 100	375 ms	8372 KiB

Main

#include <algorithm>
#include <iostream>

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

int main()
{
	int n;
	cin >> n;
	for (int i=1; i<=n; i++)
	{
		cin >> xis[i];
	}
	for (int i=1; i<=n; i++)
	{
		cin >> lis[i];
	}
	if (n<=10)
	{
		//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
	{
		cout << "IDK";
		//assume all lis are equal
		//do later
	}
}

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