Submission #827151

#	Time	Username	Problem	Language	Result	Execution time	Memory
827151		tomruk	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	201 ms	696 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(m);
		for (int j = 0; j < m; j++) {
			row[j] = -1;
		}
		answer.push_back(row);
	}
	long long maxi = -1;
	int opt1 = -1,opt2 = -1;
	for(int i = 0;i<n;i++){
		int cnt = 0;
		for(int c = 0;c<m && cnt < 2;c+=m-1){
			cnt++;
			vector<pair<int,int>> v;
			for(int j = 0;j<n;j++){
				if(i == j){
					if(c == 0){
						v.push_back({-1e9,j});
					}
					else v.push_back({1e9,j});
				}
				else{
					if(x[j][m-1] < x[i][c]){
						v.push_back({-1e9,j});
					}
					else if(x[j][0] > x[i][c]){
						v.push_back({1e9,j});
					}
					else v.push_back({x[j][m-1]-x[j][0],j});
				}
			}
			sort(v.begin(),v.end());
			long long now = 0;
			for(int j = 0;j<n/2;j++){
				now += abs(x[v[j].second][0] - x[i][c]);
				if(x[v[j].second][0] > x[i][c])
					now = -1e18;
			}
			for(int j = n/2;j<n;j++){
				now += abs(x[v[j].second][m-1] - x[i][c]);
				if(x[v[j].second][m-1] < x[i][c])
					now = -1e18;
			}
			if(now > maxi){
				maxi = now;
				opt1 = i;
				opt2 = c;
			}
		}
	}
	assert(opt1 != -1 && opt2 != -1);
	vector<pair<int,int>> v;
	for(int j = 0;j<n;j++){
		if(opt1 == j){
			if(opt2 == 0){
				v.push_back({-1e9,j});
			}
			else v.push_back({1e9,j});
		}
		else{
			if(x[j][m-1] < x[opt1][opt2]){
				v.push_back({-1e9,j});
			}
			else if(x[j][0] > x[opt1][opt2]){
				v.push_back({1e9,j});
			}
			else v.push_back({x[j][m-1]-x[j][0],j});
		}
	}
	// cout << opt1 << ' ' << opt2 << endl;
	// cout << x[opt1][opt2] << endl;
	sort(v.begin(),v.end());
	for(int j = 0;j<n/2;j++){
		answer[v[j].second][0] = 0;
	}
	for(int j = n/2;j<n;j++){
		answer[v[j].second][m-1] = 0;
	}
	allocate_tickets(answer);
	return maxi;
}

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