Submission #304771

#	Time	Username	Problem	Language	Result	Execution time	Memory
304771		peti1234	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1180 ms	98908 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
const int c=1502;
int n, m, kezd, db[c], ki, ert;
long long sum;
vector<vector<pair<int, int> > > sz;
vector<vector<int>> sol;
priority_queue<pair<int, int> > q;
long long find_maximum(int k, vector<vector<int> > x) {
    n=x.size(), m=x[0].size();
    sol.resize(n), sz.resize(n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) sol[i].push_back(-1), sz[i].push_back({x[i][j], j});
        sort(sz[i].begin(), sz[i].end());
        for (int j=0; j<k; j++) {
            sum-=sz[i][j].first;
            q.push({sz[i][m-k+j].first+sz[i][j].first, i});
        }
    }
    for (int i=0; i<n*k/2; i++) {
        db[q.top().second]++;
        sum+=q.top().first;
        q.pop();
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<db[i]; j++) {
            ki=sz[i][m-1-j].second, ert=(kezd+j)%k;
            sol[i][ki]=ert;
        }
        kezd+=db[i];
        for (int j=0; j<k-db[i]; j++) {
            ki=sz[i][j].second, ert=(kezd+j)%k;
            sol[i][ki]=ert;
        }
    }
    allocate_tickets(sol);
    return sum;
}

• 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