Submission #769055

#	Time	Username	Problem	Language	Result	Execution time	Memory
769055		boris_mihov	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	719 ms	74044 KiB

tickets

#include "tickets.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 1500 + 10;
const int INF  = 1e9;

int n, m;
int t[MAXN][MAXN];
int ans[MAXN][MAXN];
int perm[MAXN][MAXN];
std::priority_queue <std::pair <int,int>> pq;
int usedMAX[MAXN];
int usedMIN[MAXN];
int sorted[MAXN];

long long find_maximum(int k, std::vector<std::vector<int>> x) 
{
	n = x.size();
	m = x[0].size();
	
    llong ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            t[i][j] = x[i - 1][j - 1];
            perm[i][j] = j;
        }

        std::sort(perm[i] + 1, perm[i] + 1 + m, [&](int x, int y)
        {
            return t[i][x] < t[i][y];
        });

        for (int j = 1 ; j <= k ; ++j)
        {
            ans -= t[i][perm[i][j]];
        }

        usedMIN[i] = k;
        usedMAX[i] = m;
        pq.push({t[i][perm[i][usedMAX[i]]] + t[i][perm[i][usedMIN[i]]], i});
    }

    for (int flips = 1 ; flips <= n * k / 2 ; ++flips)
    {
        auto [value, idx] = pq.top();
        pq.pop();

        ans += value;
        usedMIN[idx]--;
        usedMAX[idx]--;
        if (usedMIN[idx] > 0)
        {
            pq.push({t[idx][perm[idx][usedMAX[idx]]] + t[idx][perm[idx][usedMIN[idx]]], idx});
        }
    }

    std::vector <std::vector <int>> answer(n);
    for (int i = 0 ; i < n ; ++i)
    {
        answer[i].resize(m, -1);
    }

    std::iota(sorted + 1, sorted + 1 + n, 1);
    for (int round = 0 ; round < k ; ++round)
    {
        std::sort(sorted + 1, sorted + 1 + n, [&](int x, int y)
        {
            return usedMAX[x] < usedMAX[y];
        });

        for (int i = 1 ; i <= n / 2 ; ++i)
        {
            usedMAX[sorted[i]]++;
            answer[sorted[i] - 1][perm[sorted[i]][usedMAX[sorted[i]]] - 1] = round;
        }

        for (int i = n / 2 + 1 ; i <= n ; ++i)
        {
            answer[sorted[i] - 1][perm[sorted[i]][usedMIN[sorted[i]]] - 1] = round;
            usedMIN[sorted[i]]--;
        }
    }

	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