제출 #401176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401176		srvlt	카니발 티켓 (IOI20_tickets)	C++14	27 / 100	645 ms	51412 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) begin(x),end(x)
#define SZ(x) (int)(x).size()
#define mem(x) memset(&x,y,sizeof(x))
#define ll long long
using namespace std;

ll find_maximum(int k, vector<vector<int>> x) {
	int n=SZ(x),m=SZ(x[0]);
	vector<vector<int>> answer(n,vector<int>(m,-1));
	vector<array<int,3>> vec;
	ll s=0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<k; j++) {
			s+=x[i][j+m-k];
			answer[i][j+m-k]=j;
			vec.pb({-x[i][j]-x[i][j+m-k],j,i});
		}
	}
	sort(all(vec));reverse(all(vec));
	set<array<int,2>> rows;
	for(int i=0; i<k*n/2; i++) {
		s+=vec[i][0];
		rows.insert({vec[i][1],vec[i][2]});
	}
	for(int i=0; i<k; i++) {
		assert(SZ(rows)>=n/2);
		auto it=prev(end(rows));
		vector<array<int,2>> todel;
		for(int j=0; j<n/2; j++) {
			int x=(*it)[1],y=(*it)[0];
			swap(answer[x][y],answer[x][y+m-k]);
			todel.pb(*it);
			it--;
		}
		for(auto &j:todel)
			rows.erase(j);
	}
	allocate_tickets(answer);
	return s;
}

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