Submission #418158

#	Time	Username	Problem	Language	Result	Execution time	Memory
418158		qwerasdfzxcl	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	637 ms	52880 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];
        }
	}
	int cur = 0;
	vector<int> cnt(k, 0);
	for (int z=0;z<n/2*k;z++){
        auto p = pq.top(); pq.pop();
        ret += p.first;
        int tmp = cur;
        if (LR[p.second].first) tmp = max(tmp, ans[p.second][LR[p.second].first-1]+1);
        ans[p.second][LR[p.second].first] = tmp;
        cnt[tmp]++;
        for (;cur<k && cnt[cur]==n/2;cur++);
        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});
	}
	for (int i=0;i<n;i++){
        set<int> st;
        for (int j=0;j<k;j++) st.insert(j);
        for (int j=0;j<LR[i].first;j++) st.erase(st.find(ans[i][j]));
        auto iter = st.begin();
        for (int j=LR[i].second;j<m;j++){
            ans[i][j] = *iter;
            iter++;
        }
	}
	allocate_tickets(ans);
	return ret;
}

• 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