제출 #612240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612240		erekle	카니발 티켓 (IOI20_tickets)	C++17	11 / 100	3051 ms	31072 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

	vector<vector<int>> answer(n, vector<int>(m, -1));
	long long prize = 0;

	if (m == k) {
		vector<int> cnt[2], remain[2];
		cnt[0].resize(n), cnt[1].resize(n);
		remain[0].resize(n), remain[1].resize(n);

		vector<pair<int, int>> v;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
			sort(v.begin(), v.end());
		}
		for (int i = 0; (i<<1) < n*m; ++i) {
			++cnt[0][v[i].second];
		}
		for (int i = 0; i < n; ++i) {
			cnt[1][i] = m-cnt[0][i];
			remain[0][i] = cnt[0][i];
			remain[1][i] = cnt[1][i];
		}

		for (int i = 0; i < k; ++i) {
			vector<int> zero, one, both;
			for (int j = 0; j < n; ++j) {
				if (!remain[1][j]) zero.push_back(j);
				else if (!remain[0][j]) one.push_back(j);
				else both.push_back(j);
			}

			vector<int> u;
			u.insert(u.end(), zero.begin(), zero.end());
			u.insert(u.end(), both.begin(), both.end());
			u.insert(u.end(), one.begin(), one.end());
			int used0 = 0;
			for (int y : u) {
				if (2*used0 < n) {
					prize -= x[y][cnt[0][y]-remain[0][y]];
					answer[y][cnt[0][y]-remain[0][y]] = i;
					--remain[0][y];
					++used0;
				} else {
					prize += x[y][cnt[0][y]+remain[1][y]-1];
					answer[y][cnt[0][y]+remain[1][y]-1] = i;
					--remain[1][y];
				}
			}
		}
	}
	allocate_tickets(answer);
	return prize;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10