Submission #1278060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278060		SabaKharebava	Festival (IOI25_festival)	C++20	0 / 100	1205 ms	2066932 KiB

festival

#include<bits/stdc++.h>

using namespace std;

vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
	#define pb push_back
	int n = p.size();

	vector<vector<int>> v;
	for (int i = 0; i < n; i++)
		v.pb({p[i], t[i], i});

	sort(v.begin(), v.end(), [&](vector<int> a, vector<int> b) {
		int A = -a[0]*a[1]*b[1] - b[0]*b[1];
		int B = -b[0]*a[1]*b[1] - a[0]*a[1];

		if (A == B)
			return a[0] < b[0];
		return A > B;
	});

	//cout<< "CONSTRUCTING THE DP :\n";
	vector<vector<int>> dp(n+1, vector<int> (n+1, -1));
	for (int i = 1; i <= n; i++) {
	//	cout<< "\t" << i << " -> " << (a-v[i-1][0]) * v[i-1][1] << '\n';
		dp[i][1] = (a - v[i-1][0]) * v[i-1][1];
		dp[i][0] = a;
	}

	//cout<< "\nSORTED V :\n";
	//for (vector<int> vv : v)
	//	cout<< '\t' << vv[0] << " : " << vv[1] << "\n";
	//cout<< '\n';

	//cout<< "DP :\n";
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = max(dp[i-1][j], dp[i][j]);
			dp[i][j] = max(dp[i][j], (dp[i-1][j-1] - v[i-1][0]) * v[i-1][1]);
			
	//		cout<< '\t' << dp[i][j] << ' ';
		}
	//	cout<< '\n';
	}
	//cout<< '\n';

	vector<int> ans;
	int am = n;
	while (am > 0 and dp[n][am] < 0)
		am--;
    	if (am == 0)
		return {};
    	int last = n;
	while (am > 0 and last > 0) {
		if (am == last or dp[last][am] != dp[last-1][am]) {
            		ans.pb(v[last-1][2]);
            		last--;
            		am--;
        	    	continue;
        	}
        	last--;
    	}
	reverse(ans.begin(), ans.end());

  return ans;
}

/*
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, a; cin>> n >> a;
	vector<int> p(n), t(n);

	for (int &e : p)
		cin>> e;
	for (int &e : t)
		cin>> e;

	vector<int> ans = max_coupons(a, p, t);
	cout<< ans.size() << '\n';
	for (int e : ans)
		cout<< e << ' ';
	cout<< '\n';

	return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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