Submission #827178

#	Time	Username	Problem	Language	Result	Execution time	Memory
827178		tomruk	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	614 ms	51356 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);
	}
	vector<int> as(n,0);
	long long tot = 0;
	for(int xx = 0;xx<k;xx++){
		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-xx-1){
				cnt++;
				vector<pair<int,int>> v;
				for(int j = 0;j<n;j++){
					if(i == j){
						if(cnt == 1){
							v.push_back({-2e9,j});
						}
						else v.push_back({2e9,j});
					}
					else{
						if(x[j][m-xx-1] < x[i][c]){
							v.push_back({-2e9,j});
						}
						else if(x[j][0] > x[i][c]){
							v.push_back({2e9,j});
						}
						else v.push_back({x[j][m-xx-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-xx-1] - x[i][c]);
					if(x[v[j].second][m-xx-1] < x[i][c])
						now = -1e18;
				}
				if(now > maxi){
					maxi = now;
					opt1 = i;
					opt2 = cnt;
				}
			}
		}
		assert(opt1 != -1 && opt2 != -1);
		vector<pair<int,int>> v;
		for(int j = 0;j<n;j++){
			if(opt1 == j){
				if(opt2 == 1){
					v.push_back({-2e9,j});
				}
				else v.push_back({2e9,j});
			}
			else{
				if(x[j][m-xx-1] < x[opt1][(opt2-1) * (m-xx-1)]){
					v.push_back({-2e9,j});
				}
				else if(x[j][0] > x[opt1][(opt2-1) * (m-xx-1)]){
					v.push_back({2e9,j});
				}
				else v.push_back({x[j][m-xx-1]+x[j][0],j});
			}
		}
		sort(v.begin(),v.end());
		for(int j = 0;j<n/2;j++){
			answer[v[j].second][as[v[j].second] + 0] = xx;
			as[v[j].second]++;
			x[v[j].second].erase(x[v[j].second].begin());
		}
		for(int j = n/2;j<n;j++){
			answer[v[j].second][as[v[j].second] + m-xx-1] = xx;
			x[v[j].second].erase(prev(x[v[j].second].end()));
		}
		tot += maxi;
	}
	allocate_tickets(answer);
	return tot;
}

• 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