Submission #166405

#	Time	Username	Problem	Language	Result	Execution time	Memory
166405		Sensei	Hokej (COCI17_hokej)	C++17	0 / 120	514 ms	11480 KiB

hokej

#include <bits/stdc++.h>

using namespace std;

class Player {
public:
	int K, L;
	int no;
};

class Timeline {
public:
	int t;
	vector<int> players;
};

class Substitute {
public:
	int t;
	int no1, no2;
};

Timeline timelines[6];
Player init_players[6];
vector<Substitute> substitutions;

int main () {
	int N, M;

	cin >> M >> N;

	vector<Player> players(N);

	for (int i = 0; i < N; i++) {
		cin >> players[i].K >> players[i].L;
		players[i].no = i + 1;
	}

	sort(players.begin(), players.end(), [](Player a, Player b) {
		if (a.K == b.K) {
			return a.L > b.L;
		}

		return a.K > b.K;
	});

	long long ans = 0;

	for (int i = 0; i < N; i++) {
		int best_timeline = -1;
		int best_time_on_field = 0;

		for (int t = 0; t < 6; t++) {
			int time_on_field = min(players[i].L, max(0, (M - timelines[t].t) - players[i].L));

			if (time_on_field > best_time_on_field) {
				best_timeline = t;
				best_time_on_field = time_on_field;
			}
		}

		if (best_time_on_field > 0) {
			if (timelines[best_timeline].players.size() == 0) {
				init_players[best_timeline] = players[i];
			}
			else {
				Substitute substitution;
				substitution.t = timelines[best_timeline].t;
				substitution.no1 = timelines[best_timeline].players.back();
				substitution.no2 = players[i].no;

				substitutions.push_back(substitution);
			}

			timelines[best_timeline].players.push_back(players[i].no);

			timelines[best_timeline].t += best_time_on_field;
			ans += players[i].K * best_time_on_field;
		}
	}

	cout << ans << "\n";

	for (int t = 0; t < 6; t++) {
		printf("%d%c", init_players[t].no, " \n"[t + 1 == 6]);
	}

	cout << substitutions.size() << "\n";

	for (Substitute &substitution : substitutions) {
		printf("%d %d %d\n", substitution.t, substitution.no1, substitution.no2);
	}

	return 0;
}

• Subtask 1: 0 / 120