Submission #418177

#	Time	Username	Problem	Language	Result	Execution time	Memory
418177		qwerasdfzxcl	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	617 ms	51828 KiB

tickets

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

using namespace std;
typedef long long ll;
vector<pair<int, int>> LR;

bool comp(int x, int y){
    return LR[x].first>LR[y].first;
}

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;
	LR.resize(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> idx(n);
    for (int i=0;i<n;i++) idx[i] = i;
	sort(idx.begin(), idx.end(), comp);
	vector<pair<int, int>> cnt;
	for (int i=0;i<k;i++) cnt.push_back({i, n/2});
	for (auto &i:idx){
        auto iter = cnt.begin();
        for (int j=0;j<LR[i].first;j++){
            ans[i][j] = iter->first;
            iter->second--;
            if (!(iter->second)) iter = cnt.erase(iter);
            else iter++;
        }
	}
	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