Submission #1012804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012804		pawned	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	588 ms	72020 KiB

tickets

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "tickets.h"

ll find_maximum(int K, vector<vector<int>> a_given) {
	int N = a_given.size();
	int M = a_given[0].size();
	vector<vi> a(N, vi(M, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			a[i][j] = a_given[i][j];
		}
	}

	vi fc(N, 0);	// number of + in row i
	// [0, K - 1 - fc[i]] are -, [N - fc[i], N - 1] are +
	priority_queue<ii, vector<ii>> pq;
	// {gain, pos}
	for (int i = 0; i < N; i++) {
		pq.push({a[i][K - 1] + a[i][M - 1], i});
	}
	ll total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			total -= a[i][j];
		}
	}
	for (int i = 0; i < (N * K) / 2; i++) {
//		cout<<"at "<<i<<endl;
		ll add = pq.top().fi;
		int pos = pq.top().se;
		pq.pop();
		total += add;
		fc[pos]++;
		if (fc[pos] < K)
			pq.push({a[pos][K - 1 - fc[pos]] + a[pos][M - 1 - fc[pos]], pos});
	}
/*	cout<<"total: "<<total<<endl;
	cout<<"fc: ";
	for (int i = 0; i < N; i++) {
		cout<<fc[i]<<" ";
	}
	cout<<endl;*/
	set<ii> cntp;	// current count of plus
	// stores {count plus, pos}
	for (int i = 0; i < N; i++) {
		cntp.insert({fc[i], i});
	}
/*	cout<<"cntp: "<<endl;
	for (ii p : cntp)
		cout<<p.fi<<", "<<p.se<<endl;*/
	vi cut1(N, M - 1);
	vi cut2(N, 0);
	vector<vector<int>> answer(N, vector<int>(M, -1));
	for (int i = 0; i < K; i++) {
//		cout<<"at "<<i<<endl;
		auto it = --cntp.end();
		set<ii> cntpn;	// new count plus
		for (int j = 0; j < N / 2; j++) {	// use plus
			ii curr = *it;
//			cout<<"have "<<curr.se<<", "<<cut1[curr.se]<<endl;
			answer[curr.se][cut1[curr.se]] = i;
			cut1[curr.se]--;
			cntpn.insert({curr.fi - 1, curr.se});
			it--;
		}
		for (int j = 0; j < N / 2; j++) {	// use minus
			ii curr = *it;
//			cout<<"have "<<curr.se<<", "<<cut2[curr.se]<<endl;
			answer[curr.se][cut2[curr.se]] = i;
			cut2[curr.se]++;
			cntpn.insert(curr);
			it--;
		}
		cntp = cntpn;
/*		cout<<"cntp: "<<endl;
		for (ii p : cntp)
			cout<<p.fi<<", "<<p.se<<endl;*/
	}
	allocate_tickets(answer);
	return total;
}

• 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