제출 #513876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513876		AdamGS	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	490 ms	69764 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1507;
ll T[LIM][LIM], akt[LIM], ilea[LIM], ileb[LIM], n, m;
ll find_maximum(int k, vector<vector<int>>V) {
	n=V.size();
	m=V[0].size();
	rep(i, n) rep(j, m) T[i][j]=V[i][j];
	ll sum=0;
	rep(i, n) rep(j, k) sum+=T[i][m-j-1];
	priority_queue<pair<ll,int>>q;
	rep(i, n) q.push({-T[i][0]-T[i][m-k], i});
	rep(i, n*k/2) {
		ll p=q.top().st, a=q.top().nd; q.pop();
		sum+=p;
		++akt[a];
		if(akt[a]<k) q.push({-T[a][akt[a]]-T[a][m-k+akt[a]], a});
	}
	vector<vector<int>>ans;
	rep(i, n) {
		vector<int>p;
		rep(j, m) p.pb(-1);
		ans.pb(p);
	}
	rep(i, k) {
		int a=0, b=0;
		rep(j, n) {
			if(a<n/2 && ilea[j]<akt[j]) {
				ans[j][ilea[j]]=i;
				++ilea[j];
				++a;
			} else {
				++ileb[j];
				++b;
				ans[j][m-ileb[j]]=i;
			}
		}
	}
	allocate_tickets(ans);
	return sum;
}

• 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