Submission #675489

#	Time	Username	Problem	Language	Result	Execution time	Memory
675489		VodkaInTheJar	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	434 ms	51448 KiB

tickets

#include <bits/stdc++.h>
#include <cstdio>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

void allocate_tickets(vector <vector <int> > r);
long long find_maximum(int k, vector <vector <int> > x) {
    int n = (int)x.size(), m = (int)x[0].size();
    vector <int> taken(n, k);
    long long ans = 0;
    int balance = 0; 
    priority_queue <pair <int, int> > pq; 
    for (int i = 0; i < n; i++) {
        for (int j = m - k; j < m; j++)
            ans += x[i][j];

        taken[i] = k;
        balance += k; 
        pq.push({-x[i][m-k]-x[i][0], i});
    }

    while (balance > 0) {
        pair <int, int> curr = pq.top();
        pq.pop();

        ans += curr.first;
        balance -= 2; 
        taken[curr.second]--;
        if (taken[curr.second] != 0)
            pq.push({-x[curr.second][m-taken[curr.second]]-x[curr.second][k-taken[curr.second]], curr.second});
    }

    vector <vector <int> > r(n, vector <int> (m, -1));
    vector <int> cnt0(n, 0), cnt1(n, 0);
    for (int i = 0; i < k; i++) {
        bool which = false;
        int balance = 0; 
        for (int j = 0; j < n; j++) {
            int curr0 = k - taken[j] - cnt0[j], curr1 = taken[j] - cnt1[j];
            balance += curr0 - curr1;
            if (curr0 > curr1)
                r[j][cnt0[j]] = i, cnt0[j]++;
            
            else 
                if (curr1 > curr0)
                    r[j][m-taken[j]+cnt1[j]] = i, cnt1[j]++;

                else {
                    if (!which)
                        r[j][cnt0[j]] = i, cnt0[j]++;

                    else 
                        r[j][m-taken[j]+cnt1[j]] = i, cnt1[j]++;

                    which ^= 1; 
                }
        }

        assert(balance == 0);
    }

    allocate_tickets(r);
/*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << r[i][j] << " ";

        cout << endl; 
    }
  */  

    return ans; 
}

/*
int n, m, k;
int main() {
    cin >> n >> m >> k;
    vector <vector <int> > x(n, vector <int> (m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> x[i][j];

    cout << find_maximum(k, x) << endl;
}
*/

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10