Submission #305658

#	Time	Username	Problem	Language	Result	Execution time	Memory
305658		CaroLinda	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1342 ms	101836 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

#define ff first
#define ss second
#define mk make_pair
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

using namespace std ;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	
	int n = x.size();
	int m = x[0].size();
	long long tot = 0LL ;
	
	vector< vector<int> > answer( n , vector<int>(m,-1) ) ;
	vector< vector<int> > idx(n , vector<int>(m) ) ;
	vector< pair<long long, int> > somas ;
	vector<int> peguei(n,0) ;

	for(int i = 0 ; i < n ; i++ )
	{
		iota(all(idx[i]) , 0 ) ;
		sort( all(idx[i]) , [&](int a, int b) { return x[i][a] < x[i][b] ; } ) ;

		for(int j = 0 ; j < k ; j++ ) tot -= x[i][ idx[i][j] ] ;

		for(int j = k-1 , g = m-1 ; j >= 0 ; j-- , g-- )
			somas.push_back( mk(x[i][j] + x[i][g] , i) ) ;

	}

	sort(all(somas)) ;
	reverse(all(somas)) ;
	
	for(int i = 0 ; i < (n * k)/2 ; i++ )
	{
		peguei[ somas[i].second ]++ ;
		tot += somas[i].first;
	}

	set< pii > s ;

	for(int i = 0 ; i < n ; i++ ) 
		if( peguei[i] ) s.insert( mk( -peguei[i] , i ) ) ;

	for(int round=0 ; round < k ; round++ )
	{

		vector<pii> toReInsert ;

		for(int i = 0 ; i < n/2 ; i++ )
		{
			auto topo = *s.begin() ;
			s.erase(s.begin()) ;

			if(-topo.ff != 1)
				toReInsert.push_back( mk( topo.ff +1 , topo.ss ) ) ;

			answer[ topo.ss ][ idx[topo.ss].back() ] = round ;
			idx[topo.ss].pop_back() ;

		}

		for(auto p : toReInsert) s.insert(p) ;

	}

	vector<bool> freq(m,false) ;

	for(int i = 0 ; i < n ; i++ )
	{	
		for(int j = 0 ; j < m ; j++ )
			if(answer[i][j] != -1) freq[ answer[i][j] ] = true ;

		int ptr = 0 ;

		for(int j = 0 ; j < k - peguei[i]; j++ )
		{
			while( ptr < k && freq[ptr] ) ptr++ ;
			answer[i][ idx[i][j] ] =  ptr ;
			freq[ptr] = true ;
		}

		for(int j = 0 ; j < k ; j++ ) freq[j] =false ;

	}
	
	allocate_tickets(answer);
	return tot ;
}

• 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