Submission #480121

#	Time	Username	Problem	Language	Result	Execution time	Memory
480121		couplefire	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	949 ms	60604 KiB

tickets

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

ll find_maximum(int k, vector<vector<int>> x){
    int n = x.size(), m = x[0].size();
    vector<int> stuff(n, k-1);
    set<array<int, 2>, greater<>> se; ll ans = 0;
    for(int i = 0; i<n; ++i)
        se.insert({x[i][m-1]+x[i][k-1], i});
    for(int i = 0; i<n; ++i)
        for(int j = 0; j<k; ++j)
            ans -= x[i][j];
    for(int _ = 0; _<n*k/2; ++_){
        auto [a, b] = *se.begin(); 
        se.erase(se.begin()); ans += a; stuff[b]--;
        if(stuff[b]>=0) se.insert({x[b][stuff[b]]+x[b][stuff[b]+m-k], b});
    }
    vector<vector<int>> res(n, vector<int>(m, -1));
    vector<array<int, 2>> bd(n);
    for(int i = 0; i<n; ++i)
        bd[i] = {stuff[i], stuff[i]+m-k+1};
    for(int i = 0; i<k; ++i){
        vector<int> arr(n);
        iota(arr.begin(), arr.end(), 0);
        sort(arr.begin(), arr.end(), [&](int a, int b){return bd[a]>bd[b];});
        for(int j = 0; j<n/2; ++j)
            res[arr[j]][bd[arr[j]][0]] = i, --bd[arr[j]][0];
        for(int j = n/2; j<n; ++j)
            res[arr[j]][bd[arr[j]][1]] = i, ++bd[arr[j]][1];
    }
    allocate_tickets(res); 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