Submission #757965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757965	2023-06-14T03:08:31 Z	jer033	Gym Badges (NOI22_gymbadges)	C++17	15 / 100	375 ms	8372 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	59 ms	292 KB	Output is correct
4	Correct	61 ms	212 KB	Output is correct
5	Correct	64 ms	312 KB	Output is correct
6	Correct	65 ms	304 KB	Output is correct
7	Correct	7 ms	308 KB	Output is correct
8	Correct	59 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	73 ms	292 KB	Output is correct
14	Correct	60 ms	212 KB	Output is correct
15	Correct	64 ms	300 KB	Output is correct
16	Correct	7 ms	308 KB	Output is correct
17	Correct	8 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	66 ms	292 KB	Output is correct
20	Correct	71 ms	292 KB	Output is correct

Subtask #2

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	375 ms	8372 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	59 ms	292 KB	Output is correct
4	Correct	61 ms	212 KB	Output is correct
5	Correct	64 ms	312 KB	Output is correct
6	Correct	65 ms	304 KB	Output is correct
7	Correct	7 ms	308 KB	Output is correct
8	Correct	59 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	73 ms	292 KB	Output is correct
14	Correct	60 ms	212 KB	Output is correct
15	Correct	64 ms	300 KB	Output is correct
16	Correct	7 ms	308 KB	Output is correct
17	Correct	8 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	66 ms	292 KB	Output is correct
20	Correct	71 ms	292 KB	Output is correct
21	Incorrect	5 ms	340 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	59 ms	292 KB	Output is correct
4	Correct	61 ms	212 KB	Output is correct
5	Correct	64 ms	312 KB	Output is correct
6	Correct	65 ms	304 KB	Output is correct
7	Correct	7 ms	308 KB	Output is correct
8	Correct	59 ms	300 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	73 ms	292 KB	Output is correct
14	Correct	60 ms	212 KB	Output is correct
15	Correct	64 ms	300 KB	Output is correct
16	Correct	7 ms	308 KB	Output is correct
17	Correct	8 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	66 ms	292 KB	Output is correct
20	Correct	71 ms	292 KB	Output is correct
21	Incorrect	375 ms	8372 KB	Output isn't correct
22	Halted	0 ms	0 KB	-