Submission #487674

#	Time	Username	Problem	Language	Result	Execution time	Memory
487674		alextodoran	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	683 ms	93740 KiB

tickets

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

void allocate_tickets (vector <vector <int>> sol);

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

    vector <vector <ll>> sum (n, vector <ll> (m - t + 1));
    for(int i = 0; i < n; i++)
    {
        sum[i][0] = 0;
        for(int j = t; j < m; j++)
            sum[i][0] += x[i][j];
        for(int j = 1; j < m - t + 1; j++)
            sum[i][j] = sum[i][j - 1] - x[i][j - 1] - x[i][j + t - 1];
    }

    vector <int> pos (n);
    priority_queue <pair <ll, int>> q;
    for(int i = 0; i < n; i++)
    {
        pos[i] = 0;
        if(pos[i] + 1 < (int) sum[i].size())
            q.push({sum[i][pos[i] + 1] - sum[i][pos[i]], i});
    }

    for(int it = 1; it <= k * n / 2; it++)
    {
        int i = q.top().second;
        q.pop();

        pos[i]++;
        if(pos[i] + 1 < (int) sum[i].size())
            q.push({sum[i][pos[i] + 1] - sum[i][pos[i]], i});
    }

    ll answer = 0;
    for(int i = 0; i < n; i++)
        answer += sum[i][pos[i]];

    vector <int> A (n);
    vector <int> B (n);

    for(int i = 0; i < n; i++)
    {
        A[i] = pos[i] - 1;
        B[i] = pos[i] + t;
    }

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

    vector <int> p (n);
    for(int i = 0; i < n; i++)
        p[i] = i;

    for(int step = 0; step < k; step++)
    {
        sort(p.begin(), p.end(), [&] (const int &i, const int &j)
        {
            return A[i] > A[j];
        });
        for(int i = 0; i < n / 2; i++)
        {
            sol[p[i]][A[p[i]]] = step;
            A[p[i]]--;
        }
        for(int i = n / 2; i < n; i++)
        {
            sol[p[i]][B[p[i]]] = step;
            B[p[i]]++;
        }
    }

    allocate_tickets(sol);

    return answer;
}

• 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