Submission #1022692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022692		u_suck_o	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	851 ms	133564 KiB

tickets

#include "tickets.h"
#include "bits/stdc++.h"
#define SZ 1505
 
using namespace std;

long long ans = 0;
 
long long find_maximum(int k, vector<vector<int>> x) {
    int n = x.size();
    int m = x[0].size();
    
    vector<vector<pair<int, int>>> xsorted (n, vector<pair<int, int>>(m));
    vector<vector<int>> temp (n, vector<int>(m, -1));
    vector<vector<int>> temp2 (n, vector<int>(m, -1));
    vector<vector<int>> answer (n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            xsorted[i][j] = {x[i][j], j};
        sort(xsorted[i].begin(), xsorted[i].end());
        for (int j = 0; j < k; j++)
            temp[i][j] = 0;
    }
    
    vector<pair<int, pair<int, int>>> v;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            ans -= xsorted[i][j].first;
            v.push_back({xsorted[i][m-k+j].first + xsorted[i][j].first, {i, j}});
        }
    }
    sort(v.begin(), v.end());
    for (int i = (int)v.size()-1; i >= (int)v.size() - k*n/2; i--) {
        ans += v[i].first;
        //cout << "i: " << i << " " << v[i].first << " " << ans << "\n";
        temp[v[i].second.first][v[i].second.second] = -1;
        temp[v[i].second.first][v[i].second.second+m-k] = 1;
    }
    
    set<pair<int, int>> sizes;
    for (int i = 0; i < k; i++)
        sizes.insert({0, i});
    
    for (int i = 0; i < n; i++) {
        vector<int> small;
        for (int j = 0; j < m; j++) {
            if (temp[i][j] == 0)
                small.push_back(j);
        }
        //fill in small rounds
        set<int> s; for (int j = 0; j < k; j++) s.insert(j);
        vector<pair<int, int>> rem;
        for (int j : small) {
            int round = (*sizes.begin()).second;
            temp2[i][j] = round;
            s.erase(round);
            rem.push_back(*sizes.begin());
            sizes.erase(sizes.begin());
        }
        //reset sizes
        for (auto p : rem) {
            if (p.first+1 < n/2)
                sizes.insert({p.first+1, p.second});
        }
        //fill in large rounds
        for (int j = 0; j < m; j++) {
            if (temp[i][j] == 1) {
                temp2[i][j] = *s.begin();
                s.erase(s.begin());
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            answer[i][xsorted[i][j].second] = temp2[i][j];
    }
    
    allocate_tickets(answer);
    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