Submission #758006

#	Time	Username	Problem	Language	Result	Execution time	Memory
758006		jer033	Fruits (NOI22_fruits)	C++17	11 / 100	219 ms	16728 KiB

Main

#include <algorithm>
#include <iostream>

int assigned[400005];
long long costs[400005];
long long answer[400005];
int available[400005];//boolean
int toassign[400005];//list
int avail[400005];//list

using namespace std;

int factorial(int n)
{
	if (n<=1)
		return 1;
	return n*factorial(n-1);
}

int main()
{
	int n;
	cin >> n;
	int subtwo=1;
	for (int i=1; i<=n; i++)
	{
		available[i]=1;
	}
	int mychoice=0;
	for (int i=1; i<=n; i++)
	{
		cin >> assigned[i];
		if (assigned[i]>0)
		{
			subtwo=0;
			available[assigned[i]]=0;
		}
		else
		{
			mychoice++;
			toassign[mychoice]=i;
		}
	}
	if (subtwo)
	{
		answer[0]=0;
		for (int i=1; i<=n; i++)
		{
			cin >> costs[i];
			answer[i]=answer[i-1]+costs[i];
		}
		for (int i=0; i<n; i++)
		{
			cout << answer[n]-answer[n-1-i];
			if (i!=(n-1))
				cout << ' ';
			else
				cout << '\n';
		}
	}
	else if (n<=8)
	{
		for (int i=1; i<=n; i++)
			cin >> costs[i];
		//let's assume subtask 1 holds
		int count = 0;
		for (int i=1; i<=n; i++)
		{
			if (available[i])
			{
				count++;
				avail[count]=i;
			}
		}
		int ways=factorial(count);
		
		//copy pasted code from gym badges, edited
		for (int i=1; i<=ways; i++)
		{
			//put the tuple "avail" into the "assigned" array using "toassign" and solve for each k, store answer in max
			for (int j=1; j<=count; j++)
			{
				assigned[toassign[j]]=avail[j];
			}
			
			int currbest=0;
			long long money=0;
			for (int j=1; j<=n; j++)
			{
				//cout << assigned[j];
				if (assigned[j]>currbest)
				{
					currbest=assigned[j];
					money+=costs[assigned[j]];
				}
				answer[j]=max(answer[j], money);
			}
			//cout << '\n';
			//code the next permutation
			int swapa=count-1;
			while (avail[swapa]>avail[swapa+1])
				swapa--;
			int swapb=swapa+1;
			for (int j=swapa+2; j<=count; j++)
			{
				if (avail[j]>avail[swapa])
					swapb=j;
			}
			int x=avail[swapa];
			avail[swapa]=avail[swapb];
			avail[swapb]=x;
			sort(avail+swapa+1, avail+count+1);
		}
		
		for (int i=1; i<=n; i++)
		{
			cout << answer[i];
			if (i!=n)
				cout << ' ';
			else
				cout << '\n';
		}
	}
	else
	{
		cout << "I was not made to do this.\n";
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 13
• Subtask 5: 0 / 23
• Subtask 6: 0 / 42