Submission #423861

#	Time	Username	Problem	Language	Result	Execution time	Memory
423861		humbertoyusta	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1143 ms	114616 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<int,int> ii;

vector<int> vx[1505][2];

long long find_maximum(int k, std::vector<std::vector<int>> x) {

	int n = x.size();
	int m = x[0].size();

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

	ll res = 0;

	vector<vector<ii>> mat;
	for(int i=0; i<n; i++){
        vector<ii> row(m);
        for(int j=0; j<m; j++){
            row[j] = { x[i][j] , j };
        }
        sort(all(row));
        mat.pb(row);
	}

	for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            res -= mat[i][j].f;
            fans[i][j] = 0;
        }
	}

	priority_queue<pair<int,ii>> q;

	for(int i=0; i<n; i++){
        q.push({mat[i][k-1].f + mat[i][m-1].f,{i,-1}});
	}

	for(int t=0; t<n*k/2; t++){

        pair<ll,ii> p = q.top();
        res += p.f;

        q.pop();

        fans[p.s.f][m+p.s.s] = 1;
        if( m != k ) fans[p.s.f][k+p.s.s] = -1;

        if( abs(p.s.s - 1) <= k ){
            p.s.s--;
            q.push({mat[p.s.f][k+p.s.s].f+mat[p.s.f][m+p.s.s].f,{p.s.f,p.s.s}});
        }
	}

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if( fans[i][j] == 0 ) vx[i][0].pb(j);
            if( fans[i][j] == 1 ) vx[i][1].pb(j);
        }
    }

    for(int t=0; t<k; t++){
        int cmn = n / 2, cmx = n / 2;
        vector<int> mk(n);
        for(int i=0; i<n; i++){
            if( vx[i][1].empty() ){
                mk[i] = 1;
                cmn --;
                answer[i][mat[i][vx[i][0].back()].s] = t;
                vx[i][0].pop_back();
                continue;
            }
            if( vx[i][0].empty() ){
                mk[i] = 1;
                answer[i][mat[i][vx[i][1].back()].s] = t;
                vx[i][1].pop_back();
                cmx --;
                continue;
            }
        }
        for(int i=0; i<n; i++){
            if( mk[i] ) continue;
            if( cmn > 0 ){
                cmn --;
                answer[i][mat[i][vx[i][0].back()].s] = t;
                vx[i][0].pop_back();
                continue;
            }
            if( cmx > 0 ){
                answer[i][mat[i][vx[i][1].back()].s] = t;
                vx[i][1].pop_back();
                cmx --;
                continue;
            }
        }
    }

	allocate_tickets(answer);
	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