Submission #300781

#	Time	Username	Problem	Language	Result	Execution time	Memory
300781		BaraaArmoush	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1379 ms	54392 KiB

tickets

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

using namespace std;

typedef long long ll;
typedef pair <int,int> pii;

ll find_maximum(int k, vector <vector <int>> a)
{
    int n = a.size();
    int m = a[0].size();

    vector <int> PrefixTaken(n, k);
    vector <int> SuffixTaken(n, 0);

    ll Ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < k; j++)
            Ans -= a[i][j];

    priority_queue <pair <int,pii>> q;
    for(int i = 0; i < n; i++)
        q.emplace(a[i][m - 1] + a[i][k - 1], pii(i, m - 1));

    for(int repeat = 0; repeat < k * n / 2; repeat++)
    {
        pair <int,pii> p = q.top();
        q.pop();

        int x = p.first;
        int i = p.second.first;
        int j = p.second.second;
        int r = m - j + 1;

        PrefixTaken[i]--;
        SuffixTaken[i]++;

        Ans += x;

        if(k - r >= 0)
            q.emplace(a[i][m - r] + a[i][k - r], pii(i, j - 1));
    }

    vector <vector <int>> s(n, vector <int> (m, -1));

    vector <pii> Sum(k);
    for(int j = 0; j < k; j++)  Sum[j] = pii(0, j);

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < PrefixTaken[i]; j++)
        {
            Sum[k - j - 1].first--;
            s[i][j] = Sum[k - j - 1].second;
        }

        for(int j = 0; j < SuffixTaken[i]; j++)
        {
            Sum[j].first++;
            s[i][m - j - 1] = Sum[j].second;
        }

        sort(Sum.begin(), Sum.end());
    }

    for(int j = 0; j < k; j++)
        assert(Sum[j].first == 0);

    return allocate_tickets(s), 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