Submission #541870

#	Time	Username	Problem	Language	Result	Execution time	Memory
541870		LucaDantas	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	467 ms	51476 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

	/* if(m == 1) {
		long long ans = 0;
		vector<vector<int>> build(n, vector<int>(1, 0));

		sort(x.begin(), x.end(), [](const vector<int>& v1, const vector<int>& v2) { return v1.front() < v2.front(); });

		for(int i = 0; i < n; i++)
			ans += x[i].front() * (i < n / 2 ? -1 : 1);

		allocate_tickets(build);
		return ans;
	} */

	if(k == 1) {
		long long ans = 0;
		vector<vector<int>> build(n, vector<int>(m, -1));

		// sort(x.begin(), x.end(), [](const vector<int>& v1, const vector<int>& v2) { return v1.front() < v2.front(); });

		for(int i = 0; i < n; i++)
			ans -= x[i][0], build[i][0] = 0;

		vector<pair<int,int>> opt;
		for(int i = 0; i < n; i++)
			opt.push_back({x[i].back() + x[i].front(), i});
		sort(opt.begin(), opt.end(), greater<pair<int,int>>());
		
		for(int i = 0; i < n/2; i++)
			build[opt[i].second].front() = -1, build[opt[i].second].back() = 0, ans += opt[i].first;

		allocate_tickets(build);
		return ans;
	}

	return 0;

	/* int cnt[2]{};

	for(auto v : x)
		for(int hm : v)
			cnt[hm]++; */

	/* vector<vector<int>> escolhe(n, vector<int>);

	vector<int> dp(2*n*k+1, -0x3f3f3f3f), prox = dp;
	int offset = n*k;
	dp[offset] = 0; */

	/* std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) {
			if (j < k) {
				row[j] = j;
			} else {
				row[j] = -1;
			}
		}
		answer.push_back(row);
	}
	allocate_tickets(answer); */

	// return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10