제출 #1166793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166793		MateiKing80	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	716 ms	107604 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

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

using namespace std;

int sum[1505], f[1505], b[1505];
vector<vector<int>> ret;

bool cmp(pair<long long, pair<int, int>> a, pair<long long, pair<int, int>> _b) 
{
	if (a.first != _b.first) 
		return a.first > _b.first;
	else 
		return a.second < _b.second;
}

long long find_maximum(int k, std::vector<std::vector<int>> d) 
{
	int c = d.size();
	int s = d[0].size();
	vector<pair<long long, pair<int, int>>> V;
	long long ans = 0;
	vector<vector<pair<int, int>>> d2;
	d2.resize(c);
	for (int i = 0; i < c; i ++)
		for (int j = 0; j < s; j ++)
			d2[i].push_back({d[i][j], j});
	for (int i = 0; i < c; i ++) 
	{
		sort(d2[i].begin(), d2[i].end());
		for (int j = 0; j < k; j ++) 
			V.push_back({(long long)d2[i][s - j - 1].first + d2[i][k - j - 1].first, {i, j}});
		for (int j = 0; j < k; j ++) 
			ans -= d2[i][j].first;
	}
	sort(V.begin(), V.end(), cmp);
	for (int i = 0; i < c * k / 2; i ++) 
	{
		ans += V[i].first;
		sum[V[i].second.first] = V[i].second.second + 1;
	}
	ret.resize(c, vector<int>(s, -1));
	for (int i = 0; i < k; i ++) 
	{
		vector<pair<int, int>> v;
		for (int j = 0; j < c; j ++) 
			v.push_back({sum[j], j});
		sort(v.begin(), v.end());
		for (int j = 0; j < c / 2; j ++) 
		{
			ret[v[j].second][d2[v[j].second][f[v[j].second]].second] = i;
			f[v[j].second] ++;
		}
		for (int j = c / 2; j < c; j++) 
		{
			ret[v[j].second][d2[v[j].second][s - b[v[j].second] - 1].second] = i;
			b[v[j].second] ++;
			sum[v[j].second] --;
		}
	}
	allocate_tickets(ret);
	return ans;
}

/*
static int n_;
static int m_;
static int k_;
static std::vector<std::vector<int>> d_;
static std::vector<std::vector<int>> x_;
static int called_ = 0;

static void check(bool cond, std::string message) {
	if (!cond) {
		printf("%s\n", message.c_str());
		exit(0);
	}
}


void allocate_tickets( std::vector<std::vector<int>> _d) {
	check(!called_, "allocate_tickets called more than once");
	d_ = _d;
	check((int)d_.size() == n_, "allocate_tickets called with parameter of wrong size");
	for (int i = 0; i < n_; i++) {
		check((int)d_[i].size() == m_, "allocate_tickets called with parameter of wrong size");
	}
	called_ = 1;
}

int main() {
	assert(scanf("%d %d %d", &n_, &m_, &k_) == 3);
	x_.resize(n_);
	for (int i = 0; i < n_; i++) {
		x_[i].resize(m_);
		for (int j=0; j < m_; j++) {
			assert(scanf("%d", &x_[i][j]) == 1);
		}
	}
	fclose(stdin);

	long long answer = find_maximum(k_, x_);
	check(called_, "failure to call allocate_tickets");
	printf("%lld\n", answer);
	for (int i = 0; i < n_; i++) {
		for (int j = 0; j < m_; j++) {
			if (j) printf(" ");
			printf("%d", d_[i][j]);
		}
		printf("\n");
	}
	fclose(stdout);
	return 0;
}
*/

• 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