Submission #419997

#	Time	Username	Problem	Language	Result	Execution time	Memory
419997		MohamedAhmed04	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	1162 ms	100904 KiB

tickets

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

using namespace std ;

const int MAX = 1500 + 10 ;

int cnt[MAX] ;

vector< vector<int> >sign ;
vector<int>neg[MAX] , pos[MAX] ;

vector< vector<int> >v ;
int n , m , k ;

void Allocate()
{
	vector< vector<int> >alo = vector< vector<int> >(n , vector<int>(m , -1)) ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = 0 ; j < m ; ++j)
		{
			if(sign[i][j] == 1)
				pos[i].push_back(j) ;
			else if(sign[i][j] == -1)
				neg[i].push_back(j) ;
		}
		// if(pos[i].size() + neg[i].size() != k)
		// 	while(1) ;
	}
	vector< pair<int , int> >vp ;
	for(int i = 0 ; i < k ; ++i)
	{
		vp.clear() ;
		for(int j = 0 ; j < n ; ++j)
			vp.emplace_back(neg[j].size() , j) ;
		sort(vp.begin() , vp.end()) ;
		for(int j = 0 ; j < n ; ++j)
		{
			int idx = vp[j].second ;
			if(j < n/2)
			{
				alo[idx][pos[idx].back()] = i ;
				pos[idx].pop_back() ;
			}
			else
			{
				alo[idx][neg[idx].back()] = i ;
				neg[idx].pop_back() ;
			}
		}
	}
	allocate_tickets(alo) ;
}

long long find_maximum(int K, std::vector<std::vector<int>> arr) 
{
	v = arr ;
	n = v.size() , m = v[0].size() , k = K ;
	long long ans = 0 ;
	vector< array<int , 3> >v2 ;
	sign = vector< vector<int> >(n , vector<int>(m , 0)) ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = m-1 ; j > m-1-k ; --j)
		{
			ans += v[i][j] , sign[i][j] = 1 ;
		}
		for(int j = 0 ; j < k ; ++j)
		{
			if(j <= m-1-k)
				v2.push_back({v[i][j] + v[i][m-1-k+1+j] , i , j}) ;
			else
				v2.push_back({2 * v[i][j] , i , j}) ;
		}
	}
	sort(v2.begin() , v2.end()) ;
	int taken = 0 ;
	for(auto &p : v2)
	{
		if(taken == n*k/2)
			break ;
		if(cnt[p[1]] == k)
			continue ;
		taken++ ;
		ans -= p[0] ;
		cnt[p[1]]++ ;
		sign[p[1]][p[2]] = -1 ;
		if(p[2] <= m-1-k)
			sign[p[1]][m-1-k+1+p[2]] = 0 ;
	}
	Allocate() ;
	return ans ;
}

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