Submission #300347

#	Time	Username	Problem	Language	Result	Execution time	Memory
300347		jtnydv25	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1311 ms	72212 KiB

tickets

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

#define ll long long

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<ll>> f(n, vector<ll> (k + 1, 0));
	vector<int> pluses(n);
	vector<int> minuses(n);
	set<pair<ll, int>> benefits;

	ll mx = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++) f[i][0] -= x[i][j];
		for(int r = 1; r <= k; r++){
			f[i][r] = f[i][r - 1] + x[i][m - r] + x[i][k - r]; // f is concave :)
		}
		benefits.insert({f[i][1] - f[i][0], i});
		minuses[i] = k;
		mx += f[i][0];
	}

	for(int r = 1; r <= (n * k) / 2; r++){
		auto it = *benefits.rbegin();
		benefits.erase(it);
		int i = it.second;
		mx += it.first;
		pluses[i]++;
		minuses[i]--;
		if(pluses[i] != k) benefits.insert({f[i][pluses[i] + 1] - f[i][pluses[i]], i});
	}

	vector<vector<int>> when(n, vector<int>(m, -1));
	for(int r = 0; r < k; r++){
		// choose n / 2 pluses, n / 2 minuses
		vector<int> perm(n, 0);
		iota(perm.begin(), perm.end(), 0);
		vector<int> hasOption(n);
		for(int i = 0; i < n; i++) hasOption[i] = pluses[i] && minuses[i];
		sort(perm.begin(), perm.end(), [&](int i, int j){return hasOption[i] < hasOption[j];});
		int balance = 0;
		for(int i : perm){
			if(balance <= 0){
				if(pluses[i]){
					when[i][m - pluses[i]] = r;
					pluses[i]--;
					balance++;
				} else{
					when[i][--minuses[i]] = r;
					balance--;
				}
				
			} else{
				if(minuses[i]){
					when[i][--minuses[i]] = r;
					balance--;
				} else{
					when[i][m - pluses[i]] = r;
					pluses[i]--;
					balance++;
				}
			}
		}
		assert(balance == 0);
	}
	allocate_tickets(when);
	return mx;
}

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