Submission #1034175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034175		happy_node	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	433 ms	76256 KiB

tickets

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

typedef long long ll;

const int MX=1505;

int F[MX], B[MX], f[MX], b[MX];

int N,M;

long long find_maximum(int K, std::vector<std::vector<int>> d) {
        N=d.size();
        M=d[0].size();      

        priority_queue<pair<int,int>> pq;

        ll ans=0;
        for(int i=0;i<N;i++) {
                B[i]=M-K;
                for(int j=B[i];j<M;j++) ans+=d[i][j];
                pq.push({-d[i][B[i]]-d[i][F[i]],i});
        }

        int ops=N*K/2;
        while(pq.size() && ops>0) {
                auto [x,r]=pq.top(); pq.pop();

                ans+=x;
                F[r]++;
                B[r]++;
                ops--;

                if(B[r]<M) 
                        pq.push({-d[r][B[r]]-d[r][F[r]],r});
        }

        vector<pair<int,int>> v;

        for(int i=0;i<N;i++) {
                F[i]--;
                f[i]=0;
                b[i]=M-1;
                v.push_back({F[i],i});
        }

        vector<vector<int>> s(N,vector<int>(M,-1));

        for(int x=0;x<K;x++) {
                sort(v.rbegin(),v.rend());

                for(int j=0;j<N/2;j++) {
                        auto &[y,i]=v[j];
                        s[i][f[i]]=x;
                        f[i]++;
                        y--;
                }
                for(int j=N/2;j<N;j++) {
                        auto &[y,i]=v[j];
                        s[i][b[i]]=x;
                        b[i]--;
                }
        }

        allocate_tickets(s);

        return ans;
}

• 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