Submission #423748

#	Time	Username	Problem	Language	Result	Execution time	Memory
423748		humbertoyusta	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	677 ms	77984 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;

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] = j;
        }
	}

	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] = fans[p.s.f][k+p.s.s];
        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++){
            answer[i][mat[i][j].s] = fans[i][j];
            //db(fans[i][j])
        }

	allocate_tickets(answer);
	return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10