Submission #423772

#	Time	Username	Problem	Language	Result	Execution time	Memory
423772		humbertoyusta	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	714 ms	77924 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] = 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}});
        }
	}

	vector<int> mx(k), mn(k);
	for(int i=0; i<k; i++)
        mn[i] = mx[i] = n / 2;

    for(int i=0; i<n; i++){
        int c1 = 0, c2 = 0;
        for(int j=0; j<m; j++){
            if( fans[i][j] == 0 ){
                while( mn[c1] == 0 ) c1 = ( c1 + 1 ) % k;
                answer[i][j] = c1;
                mn[c1] --;
                c1 = ( c1 + 1 ) % k;
            }
            if( fans[i][j] == 1 ){
                while( mx[c1] == 0 ) c1 = ( c1 + 1 ) % k;
                answer[i][j] = c1;
                mx[c1] --;
                c1 = ( c1 + 1 ) % k;
            }
        }
    }

	allocate_tickets(answer);
	return res;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:73:21: warning: unused variable 'c2' [-Wunused-variable]
   73 |         int c1 = 0, c2 = 0;
      |                     ^~

• 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