Submission #980287

#	Time	Username	Problem	Language	Result	Execution time	Memory
980287		12345678	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	620 ms	76520 KiB

tickets

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

using namespace std;

#define ll long long

const int nx=1505;

ll N, M, res, l[nx], r[nx], cnt;
priority_queue<pair<ll, ll>> pq;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	N=x.size();
    M=x[0].size();
    vector<vector<int>> t(N, vector<int> (M));
    cnt=k*N/2;
    for (int i=0; i<N; i++) for (int j=0; j<k; j++) res-=x[i][j];
    for (int i=0; i<N; i++) l[i]=k-1, r[i]=M-1, pq.push({x[i][l[i]]+x[i][r[i]], i});
    while (cnt--)
    {
        auto tmp=pq.top();
        pq.pop();
        res+=tmp.first;
        int i=tmp.second;
        l[i]--;
        r[i]--;
        if (l[i]==-1) continue;
        pq.push({x[i][l[i]]+x[i][r[i]], i});
    }
    for (int i=0; i<N; i++) r[i]++;
    //for (int i=0; i<N; i++) printf("debug %d %d %d\n", i, l[i], r[i]);
    for (int i=0; i<N; i++) for (int j=l[i]+1; j<r[i]; j++) t[i][j]=-1;
    for (int i=0; i<k; i++)
    {
        vector<int> vs(N);
        vector<pair<int, int>> v;
        for (int j=0; j<N; j++) v.push_back({l[j]+1, j});
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        for (int j=0; j<N/2; j++) t[v[j].second][l[v[j].second]]=i, l[v[j].second]--, vs[v[j].second]=1;
        for (int j=0; j<N; j++) if (!vs[j]) t[j][r[j]]=i, r[j]++;
    }
    allocate_tickets(t);
    return res;
}

• 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