Submission #826457

#	Time	Username	Problem	Language	Result	Execution time	Memory
826457		amunduzbaev	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	2027 ms	157828 KiB

tickets

#include "tickets.h"

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

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

const int inf = 1e9;

/*

4 3 2
0 3 8
1 8 10
1 6 8
6 6 7

*/

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	
	ll ans = -1, M = -1;
	
	vector<int> lor_(n);
	
	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++){
			for(int j=0;j<k;j++){
				int l = j + m - k;
				if(x[i][l] < mid){
					res += (mid - x[i][j]);
					lor[i]++; all[0]++;
					continue;
				}
				if(mid < x[i][j]){
					res += (x[i][l] - mid);
					all[1]++;
					continue;
				}
				
				lor[i]++;
				all[0]++;
				res += mid - x[i][j];
				diff.push_back({-(mid - x[i][j]) + (x[i][l] - mid), i});
			}
		}
		
		if(all[1] * 2 > n * k || (all[1] + (int)diff.size()) * 2 < n * k) return;
		sort(diff.begin(), diff.end());
		
		while(all[1] * 2 < n * k){
			int i = diff.back()[1]; //, j = diff.back()[1] % m;
			res += diff.back()[0];
			diff.pop_back();
			lor[i]--;
			all[1]++;
		}
		
		if(all[1] * 2 != n * k) assert(false);
		
		if(res > ans){
			ans = res;
			M = mid;
			lor_ = lor;
		}
	};
	
	auto get = [&](vector<int>& lor){
		vector<vector<int>> ans(n, vector<int>(m, -1));
		vector<vector<int>> used(n, vector<int>(m));
		
		vector<int> l(n), r(n);
		for(int i=0;i<n;i++){
			for(int j=0;j<lor[i];j++) used[i][j] = 1;
			for(int j=m-(k - lor[i]);j<m;j++) used[i][j] = 1;
			
			l[i] = 0, r[i] = m - 1;
		}
		
		for(int c=0;c<k;c++){
			ar<int, 2> all {};
			queue<int> q;
			for(int i=0;i<n;i++){
				while(!used[i][l[i]]) l[i]++;
				while(!used[i][r[i]]) r[i]--;
				
				if(r[i] < lor[i]){
					ans[i][l[i]] = c;
					l[i]++; all[0]++;
				} else if(lor[i] <= l[i]){
					ans[i][r[i]] = c;
					r[i]--; all[1]++;
				} else {
					ans[i][l[i]] = c;
					l[i]++, all[0]++;
					q.push(i);
				}
			}
			
			assert(all[1] * 2 <= n);
			
			while(!q.empty() && all[1] * 2 < n){
				int i = q.front(); q.pop();
				all[1]++;
				ans[i][--l[i]] = -1;
				ans[i][r[i]--] = c;
			}
			
			assert(all[1] * 2 == n);
		}
		
		return ans;
	};
	
	vector<int> tot;
	for(int i=0;i<n;i++) tot.insert(tot.end(), x[i].begin(), x[i].end());
	
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	
	ll res = 0;
	vector<ar<int, 2>> q;
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			int l = j + m - k;
			q.push_back({x[i][j], i * m + j});
			q.push_back({x[i][l] + 1, -i * m - j - 1});
			//~ cout<<x[i][j]<<" "<<x[i][l]<<"\n";
			res += x[i][l];
		}
	}
	
	sort(q.begin(), q.end());
	multiset<int> L, R;
	ll mx = 0;
	int l_ = 0, r_ = n * k, h = n * k / 2;
	
	auto norm = [&](){
		while((int)R.size() > max(0, h - r_)){
			mx -= (*R.begin());
			L.insert(*R.begin());
			R.erase(R.begin());
		}
		while((int)R.size() < max(0, h - r_) && !L.empty()){
			mx += (*--L.end());
			R.insert(*--L.end());
			L.erase(--L.end());
		}
	};
	
	auto add = [&](int x){
		R.insert(x); 
		mx += x;
		L.insert(*R.begin());
		mx -= (*R.begin());
		R.erase(R.begin());
	};
	
	auto del = [&](int x){
		if(L.count(x)){
			L.erase(L.find(x));
		} else {
			R.erase(R.find(x));
			mx -= x;
		}
	};
	
	//~ cout<<"here"<<endl;
	
	//~ cout<<res<<endl;
	
	int j = 0;
	for(auto mid : tot){
		while(j < (int)q.size() && q[j][0] <= mid){
			if(q[j][1] >= 0){
				int i = q[j][1] / m, j_ = q[j][1] % m;
				int l = m + j_ - k;
				
				res -= x[i][l] + x[i][j_];
				add(x[i][j_] + x[i][l]);
				r_--;
			} else {
				int i = (-q[j][1] - 1) / m, j_ = (-q[j][1] - 1) % m;
				int l = m + j_ - k;
				
				del(x[i][j_] + x[i][l]);
				l_++;
			}
			norm();
			
			j++;
		}
		
		//~ cout<<mid<<" "<<l_<<" "<<r_<<" "<<h<<" "<<ans<<" "<<res<<" "<<mx<<"\n";
		
		if(l_ <= h && r_ <= h){
			if(ans < res + mx){
				ans = res + mx;
				M = mid;
			}
		}
	}
	
	assert(~M);
	
	//~ cout<<M<<endl;
	
	ans = -1;
	check(M);
	
	allocate_tickets(get(lor_));
	return ans;
	
}

• 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