Submission #1179281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179281		Pacybwoah	카니발 티켓 (IOI20_tickets)	C++20	100 / 100	481 ms	72124 KiB

tickets

#include "tickets.h"
#include <vector>
#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
typedef long long ll;

long long find_maximum(int k, std::vector<std::vector<int>> xx) {
	int n = (int)xx.size();
	int m = (int)xx[0].size();
	vector<vector<ll>> vec(n, vector<ll>(m));
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) vec[i][j] = xx[i][j];
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<int> l(n, 0), r(n, m - k);
	priority_queue<pair<ll, int>> pq;
	ll sum = 0;
	for(int i = 0; i < n; i++){
		for(int j = m - k; j < m; j++){
			sum += vec[i][j];
		}
		pq.emplace(-vec[i][m - k] - vec[i][0], i);
	}
	int times = n * k / 2;
	for(int i = 0; i < times; i++){
		auto [val, id] = pq.top();
		//cout << val << " " << id << '\n';
		pq.pop();
		sum += val;
		l[id]++;
		r[id]++;
		if(r[id] < m){
			pq.emplace(-vec[id][r[id]] - vec[id][l[id]], id);
		}
	}
	vector<pair<pair<int, int>, int>> srtd;
	for(int i = 0; i < n; i++){
		srtd.emplace_back(make_pair(l[i] - 1, r[i]), i);
	}
	for(int rnd = 0; rnd < k; rnd++){
		sort(srtd.begin(), srtd.end());
		for(int i = 0; i < n / 2; i++){
			int id = srtd[i].second;
			auto &[l, r] = srtd[i].first;
			ans[id][r] = rnd;
			r++;
		}
		for(int i = n / 2; i < n; i++){
			int id = srtd[i].second;
			auto &[l, r] = srtd[i].first;
			ans[id][l] = rnd;
			l--;
		}
	}
	allocate_tickets(ans);
	return sum;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g grader.cpp tickets.cpp

• 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