Submission #826115

#	Time	Username	Problem	Language	Result	Execution time	Memory
826115		amunduzbaev	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	539 ms	52580 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> l(n), r(n, m - 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][r[i]] < mid || mid < x[i][l[i]]){
				if(mid < x[i][l[i]]) all[1]++, res += x[i][r[i]] - mid, lor[i] = 1;
				else all[0]++, res += mid - x[i][l[i]];
				continue;
			}
			
			all[0]++;
			res += mid - x[i][l[i]];
			diff.push_back({(x[i][r[i]] - mid) - (mid - x[i][l[i]]), 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;
		}
	};
	
	ll tot = 0;
	
	vector<vector<int>> res(n, vector<int>(m, -1));
	for(int c=0;c<k;c++){
		ans = -1;
		for(int i=0;i<n;i++){
			check(x[i][l[i]]);
			check(x[i][r[i]]);
		}
		
		tot += ans;
		for(int i=0;i<n;i++){
			if(lor_[i]) res[i][r[i]] = c, r[i]--;
			else res[i][l[i]] = c, l[i]++;
		}
	}
	
	allocate_tickets(res);
	return tot;
}

• 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