Submission #1281669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281669		dimitri.shengelia	Festival (IOI25_festival)	C++20	5 / 100	113 ms	17212 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {

	long long x = A;

	int n = P.size();

	vector <int> v;

	multiset <pair <long long, int>> st1, st2, st3, st4;

	for ( int i = 0; i < n; i++ ) {

		if ( T[i] == 1 ) {

			st1.insert( { P[i], i } );

		} else if ( T[i] == 2 ) {

			st2.insert( { (long long)P[i] * 2, i } );

		} else if ( T[i] == 3 ) {

			st3.insert( { (long long)P[i] * 3, i } );

		} else {

			st4.insert( { (long long)P[i] * 4, i } );

		}

	}

	while ( x >= 0 ) {

		long long mx = -1;

		long long a1 = 0, a2 = 0, a3 = 0, a4 = 0;

		if ( st1.size() > 0 ) {
			a1 = x - st1.begin()->first;
			mx = a1;
		}
		if ( st2.size() > 0 ) {
			a2 = x * 2 - st2.begin()->first;
			mx = max( mx, a2 );
		}
		if ( st3.size() > 0 ) {
			a3 = x * 3 - st3.begin()->first;
			mx = max( mx, a3 );
		}
		if ( st4.size() > 0 ) {
			a4 = x * 4 - st4.begin()->first;
			mx = max( mx, a4 );
		}

		if ( mx < 0 ) {
			break;
		} else if ( st1.size() > 0 and a1 == mx ) {
			v.push_back( st1.begin()->second );
			st1.erase( st1.begin() );
			x = a1;
		} else if ( st2.size() > 0 and a2 == mx ) {
			v.push_back( st2.begin()->second );
			st2.erase( st2.begin() );
			x = a2;
		} else if ( st3.size() > 0 and a3 == mx ) {
			v.push_back( st3.begin()->second );
			st3.erase( st3.begin() );
			x = a3;
		} else if ( st4.size() > 0 and a4 == mx ) {
			v.push_back( st4.begin()->second );
			st4.erase( st4.begin() );
			x = a4;
		}

	}

	return v;

}

/*int main() {

	int n, a;
	cin >> n >> a;

	vector <int> p, t;

	for ( int i = 0; i < n; i++ ) {

		int x;
		cin >> x;

		p.push_back( x );

	}

	for ( int i = 0; i < n; i++ ) {

		int x;
		cin >> x;

		t.push_back( x );

	}

	vector <int> answer = max_coupons( a, p, t );

	cout << answer.size() << "\n";

	for ( int i = 0; i < answer.size() - 1; i++ ) {

		cout << answer[i] << " ";

	}

	if ( answer.size() > 0 ) {

		cout << answer[answer.size() - 1] << "\n";

	}

	return 0;

}*/

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18