oj.uz

Submission #757957

# Submission time Handle Problem Language Result Execution time Memory
757957 2023-06-14T02:50:40 Z jer033 Gym Badges (NOI22_gymbadges) C++17
0 / 100
 1 ms 212 KB 
#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)
	{
		//code the brute force
		for (int i=0; i<n; i++)
		{
			cin >> xis[i];
		}
		for (int i=0; i<n; i++)
		{
			cin >> lis[i];
		}
		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++)
		{
			//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;
			//check how far it goes
			int badgec=1;
			long long level=xis[permu[1]];
			while (badgec<n and level<=lis[permu[badgec+1]])
			{
				badgec++;
				level+=xis[permu[badgec]];
			}
			maxbadges=max(maxbadges, badgec);
		}
		cout << maxbadges << '\n';
	}
	else
	{
		cout << "IDK";
		//assume all lis are equal
		//do later
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 Incorrect 1 ms 212 KB Output isn't correct
3 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -