Submission #826101

#	Time	Username	Problem	Language	Result	Execution time	Memory
826101		amunduzbaev	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	566 ms	73036 KiB

tickets

#include "tickets.h"

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

#define ar array
typedef long long ll;
//~ #define int ll

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	
	ll ans = -1;
	
	vector<int> lor_;
	
	auto check = [&](int mid){
		ll res = 0;
		ar<int, 2> all {};
		vector<ar<int, 2>> diff;
		
		vector<int> lor(n);
		
		for(int i=0;i<n;i++){
			if(x[i][m - 1] < mid || mid < x[i][0]){
				if(mid < x[i][0]) all[1]++, res += x[i][m - 1] - mid, lor[i] = 1;
				else all[0]++, res += mid - x[i][0];
				continue;
			}
			
			all[0]++;
			res += mid - x[i][0];
			diff.push_back({(x[i][m - 1] - mid) - (mid - x[i][0]), i});
		}
		
		if(all[1] * 2 > n || (all[1] + (int)diff.size()) * 2 < n) return;
		sort(diff.begin(), diff.end());
		
		while(all[1] * 2 < n){
			all[0]--;
			all[1]++;
			res += diff.back()[0];
			lor[diff.back()[1]] = 1;
			diff.pop_back();
		}
		
		if(ans < res){
			ans = res;
			lor_ = lor;
		}
	};
	
	for(int i=0;i<n;i++){
		check(x[i][0]);
		check(x[i][m - 1]);
	}
	
	vector<vector<int>> res(n, vector<int>(m, -1));
	for(int i=0;i<n;i++){
		if(lor_[i]) res[i][m - 1] = 0;
		else res[i][0] = 0;
	}
	
	allocate_tickets(res);
	return ans;
}

• 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