Submission #1050763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050763		Huseyn123	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	515 ms	54352 KiB

tickets

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std; 
typedef long long ll; 
ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ll res=0;
	vector<vector<int>> answer; 
	for(int i=0;i<n;i++){
		vector<int> d; 
		for(int j=0;j<m;j++){
			d.pb(-1);
		}
		answer.pb(d);
	}
	int pre[n],suf[n];
	for(int i=0;i<n;i++){
		pre[i]=k; 
		suf[i]=0;
		for(int j=0;j<k;j++){
			res-=x[i][j]; 
		}
	}
	set<pair<ll,int>> c;
	for(int i=0;i<n;i++){
		if(pre[i]==0){
			continue;
		}
		ll val=x[i][m-suf[i]-1]+x[i][pre[i]-1];
		c.insert({val,i});
	}
	for(int i=0;i<k*(n/2);i++){
		pair<ll,int> p=*(--c.end());
		c.erase(p);
		res+=p.first;
		int j=p.second;
		pre[j]--;
		suf[j]++;
		if(pre[j]==0){
			continue;
		}
		ll val=x[j][m-suf[j]-1]+x[j][pre[j]-1];
		c.insert({val,j});
	}
	for(int i=0;i<k;i++){
		vector<pair<int,int>> d;
		for(int j=0;j<n;j++){
			d.pb({suf[j],j});
		}
		sort(d.rbegin(),d.rend());
		for(int j=0;j<n/2;j++){
			answer[d[j].second][m-d[j].first]=i;
			suf[d[j].second]--;
		}
		for(int j=n/2;j<n;j++){
			answer[d[j].second][pre[d[j].second]-1]=i;
			pre[d[j].second]--;
		}
	}
	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