oj.uz

Submission #758003

# Submission time Handle Problem Language Result Execution time Memory
758003 2023-06-14T04:37:07 Z jer033 Fruits (NOI22_fruits) C++17
5 / 100
 219 ms 17096 KB 
#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<=2)
		return n;
	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 12 ms 1076 KB Output is correct
4 Correct 127 ms 8628 KB Output is correct
5 Correct 219 ms 17096 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -