Submission #499821

#	Time	Username	Problem	Language	Result	Execution time	Memory
499821		benson1029	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	469 ms	51480 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long ans1 = 0;
int ptr1[1505], ptr2[1505];
int used[1505];
set<int> used2[1505];
priority_queue< pair<long long, int> > pq;
vector< vector<int> > ans2;
vector<int> ord;

bool cmp(int x, int y) {
    return ptr1[x] > ptr1[y];
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	for(int i=0; i<n; i++) {
        for(int j=0; j<k; j++) {
            ans1 -= x[i][j];
        }
        ptr1[i] = k-1;
        ptr2[i] = m-1;
        pq.push({x[i][ptr1[i]]+x[i][ptr2[i]], i});
    }
    for(int i=0; i<k*(n/2); i++) {
        int curr = pq.top().second;
        ans1 += pq.top().first;
        pq.pop();
        ptr1[curr]--;
        ptr2[curr]--;
        if(ptr1[curr] >= 0) {
            pq.push({x[curr][ptr1[curr]]+x[curr][ptr2[curr]], curr});
        }
    }
    ans2.resize(n);
    for(int i=0; i<n; i++) {
        ans2[i].resize(m);
        for(int j=0; j<m; j++) {
            ans2[i][j] = -1;
        }
        for(int j=0; j<k; j++) used2[i].insert(j);
        ord.push_back(i);
    }
    sort(ord.begin(), ord.end(), cmp);
    for(int i:ord) {
        int tmp = 0;
        for(int j=0; j<=ptr1[i]; j++) {
            while(used[tmp] == n/2) tmp++;
            ans2[i][j] = tmp;
            used[tmp]++;
            used2[i].erase(tmp);
            tmp++;
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=ptr2[i]+1; j<m; j++) {
            ans2[i][j] = (*used2[i].begin());
            used2[i].erase(used2[i].begin());
        }
    }
    allocate_tickets(ans2);
	return ans1;
}

• 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