Submission #398511

#	Time	Username	Problem	Language	Result	Execution time	Memory
398511		blue	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1148 ms	84944 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N, M, K;

vector< vector<int> > X;
vector<int> mv(1500, 0);

struct col
{
    int i;
};

bool operator < (col A, col B)
{
    int a = X[A.i][K-1 - mv[A.i]] + X[A.i][M-1 - mv[A.i]];
    int b = X[B.i][K-1 - mv[B.i]] + X[B.i][M-1 - mv[B.i]];

    if(a == b) return A.i < B.i;
    else return a > b;
}


vector<int> ct_top(1500), ct_bottom(1500);




long long find_maximum(int k, vector< vector<int> > x)
{
    X = x;
    K = k;
    N = x.size();
    M = x[0].size();

    set<col> S;
    for(int i = 0; i < N; i++) S.insert(col{i});

    for(int i = 0; i < N*K/2; i++)
    {
        // cerr << "move = " << i << '\n';
        // for(col q:S) cerr << q.i << ' ' << mv[q.i] << ' ' << X[q.i][K-1 - mv[q.i]] + X[q.i][M-1 - mv[q.i]] << '\n';

        int s = S.begin()->i;
        S.erase(S.begin());
        mv[s]++;
        if(mv[s] < K)
            S.insert(col{s});
    }

    // for(int i = 0; i < N; i++) cerr << mv[i] << ' ';
    // cerr << '\n';

    long long res = 0;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < K - mv[i]; j++)
            res -= X[i][j];

        for(int j = M - mv[i]; j < M; j++)
            res += X[i][j];
    }


    vector< vector<int> > s(N, vector<int>(M, -1));

    for(int i = 0; i < N; i++)
    {
        ct_top[i] = mv[i];
        ct_bottom[i] = K - ct_top[i];
    }

    vector<int> I(N);
    for(int i = 0; i < N; i++) I[i] = i;

    for(int k = 0; k < K; k++)
    {
        sort(I.begin(), I.end(), [] (int c1, int c2)
        {
            return ct_top[c1] < ct_top[c2];
        });

        for(int i = 0; i < N/2; i++)
        {
            s[I[i]][ct_bottom[I[i]] - 1] = k;
            ct_bottom[I[i]]--;
        }
        for(int i = N/2; i < N; i++)
        {
            s[I[i]][M - ct_top[I[i]]] = k;
            ct_top[I[i]]--;
        }
    }
    allocate_tickets(s);

    return res;
}

• 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