Submission #1050493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050493		noyancanturk	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	353 ms	51584 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using lint=long long;
using pii=pair<int,int>;

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;
	for(int i=0;i<n;i++){
		answer.pb(vector<int>(m,-1));
	}
	if(k==1){
		int mini[n]{},maxi[n]{};
		vector<int>vals;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(x[i][j]<x[i][mini[i]])mini[i]=j;
				if(x[i][j]>x[i][maxi[i]])maxi[i]=j;
			}
			vals.pb(x[i][mini[i]]);
			vals.pb(x[i][maxi[i]]);
		}	
		lint ans=0;
		vector<int>choices;
		for(int med:vals){
			lint cur=0;
			int cnt=0;
			vector<int>curchoice(n);
			vector<pii>des;
			for(int i=0;i<n;i++){
				if(med<x[i][mini[i]]){
					cur+=abs(med-x[i][maxi[i]]);
					//cerr<<x[i][maxi[i]]<<" maxi?\n";;
					curchoice[i]=1;
					cnt++;
				}
				else if(x[i][maxi[i]]<=med){
					cur+=abs(med-x[i][mini[i]]);
					curchoice[i]=0;
					cnt--;
				}else{
					//cerr<<i<<" is choice\n";
					cur+=abs(med-x[i][mini[i]]);
					des.pb({abs(med-x[i][maxi[i]])-abs(med-x[i][mini[i]]),i});
				}
			}
			if(des.size()<abs(cnt)){
				continue;
			}
			sort(des.begin(),des.end());
			int l=0,r=des.size()-1;
			//cerr<<med<<" :: "<<cur<<"\n";
			while(l<=r){
				if(cnt<0){
					cur+=des[r].first;
					cnt++;
					curchoice[des[r].second]=1;
					r--;
				}else{
					//cur+=des[l].first;
					cnt--;
					curchoice[des[l].second]=0;
					l++;
				}
			}
			if(ans<cur){
				ans=cur;
				//cerr<<med<<" is chosen\n";
				choices=curchoice;
			}
		}
		for(int i=0;i<n;i++){
			answer[i][choices[i]==1?maxi[i]:mini[i]]=0;
		}
		allocate_tickets(answer);
		return ans;
	}
	return -1;
}

• 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