Submission #418189

#	Time	Username	Problem	Language	Result	Execution time	Memory
418189		qwerasdfzxcl	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	906 ms	60568 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> ans;
	ans.resize(n);
	for (int i=0;i<n;i++){
        ans[i].resize(m);
        fill(ans[i].begin(), ans[i].end(), -1);
	}
	ll ret = 0;
	vector<pair<int, int>> LR(n);
	fill(LR.begin(), LR.end(), make_pair(0, m-k));

	priority_queue<pair<ll, int>> pq;
	for (int i=0;i<n;i++){
        pq.push({-x[i][LR[i].first]-x[i][LR[i].second], i});
        for (int j=LR[i].second;j<m;j++){
            ret += x[i][j];
        }
	}

	for (int z=0;z<n/2*k;z++){
        auto p = pq.top(); pq.pop();
        ret += p.first;
        LR[p.second].first++, LR[p.second].second++;
        if (LR[p.second].second<m) pq.push({-x[p.second][LR[p.second].first]-x[p.second][LR[p.second].second], p.second});
	}

	vector<int> pos(n, 0);
    for (int z=0;z<k;z++){
        vector<bool> chk(n, 0);
        vector<pair<int, int>> tmp;
        for (int i=0;i<n;i++) tmp.emplace_back(LR[i].first, i);
        sort(tmp.begin(), tmp.end());
        for (int i=n/2;i<n;i++) chk[tmp[i].second] = 1;
        for (int i=0;i<n;i++){
            if (chk[i]) ans[i][pos[i]] = z, pos[i]++, LR[i].first--;
            else ans[i][LR[i].second] = z, LR[i].second++;
        }
    }
	allocate_tickets(ans);
	return ret;
}

• 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