제출 #605225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605225		Tigryonochekk	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	463 ms	51304 KiB

tickets

#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<ll, int>

vector<vector<int>> answer;
ll ans;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(m, -1);
	}
	if (k == 1) {
		vector<pii> d(n);
		for (int i = 0; i < n; i++) {
			d[i] = pii(x[i][m - 1] + x[i][0], i);
			ans += x[i][m - 1];
		}
		sort(d.begin(), d.end());
		vector<int> v(n);
		for (int i = 0; i < n / 2; i++) {
			int ind = d[i].second;
			answer[ind][0] = 0;
			ans -= d[i].first;
		}
		for (int i = n / 2; i < n; i++) {
			int ind = d[i].second;
			answer[ind][m - 1] = 0;
		}
	}
	else if (k == m) {
		vector<pii> all;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				all.push_back(pii(x[i][j], i * m + j));
			}
		}
		sort(all.begin(), all.end());
		/*for (int i = 0; i < n * m / 2; i++) {
			ans -= all[i].first;
		}
		for (int i = n * m / 2; i < n * m; i++) {
			ans += all[i].first;
		}*/
		pii mid = all[n * m / 2];
		//ashxatum a
		vector<int> ty(n);
		for (int i = 0; i < n; i++) {
			if (pii(x[i][0], i * m) >= mid) {
				ty[i] = 1;
			}
			else if (pii(x[i][m - 1], i * m + m - 1) < mid) {
				ty[i] = 2;
			}
		}
		//ashxatum a
		//cout << "__________\n";
		vector<int> plyus(n, m - 1), minus(n);
		for (int j = 0; j < m; j++) {
			int a = 0, b = 0;
			for (int i = 0; i < n; i++) {
				if (ty[i] == 1) {
					a++;
					answer[i][j] = j;
				}
				if (ty[i] == 2) {
					b++;
					answer[i][j] = j;
				}
			}
			for (int i = 0; i < n; i++) {
				if (!ty[i]) {
					if (a < n / 2 && pii(x[i][plyus[i]], i * m + plyus[i]) >= mid) {
						answer[i][plyus[i]] = j;
						plyus[i]--;
						a++;
					}
					else {
						answer[i][minus[i]] = j;
						minus[i]++;
						b++;
					}
				}
			}
		}
		vector<vector<int>> wtf(m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				wtf[answer[i][j]].push_back(x[i][j]);
			}
		}
		for (int j = 0; j < m; j++) {
			sort(wtf.begin(), wtf.end());
			ll mid = wtf[j][n / 2];
			for (int i = 0; i < n; i++) {
				ans += abs(mid - wtf[j][i]);
			}
		}
	}
	//cout << "__________\n";
	allocate_tickets(answer);
	return ans;
}

/*
6 4 4 
1 3 6 7 
2 2 3 5 
5 6 7 8 
1 8 8 9 
3 4 6 7 
2 3 3 3 

2 2 2 
1 4 
2 3 

2 2 2 
1 3 
2 4  

2 2 2 
1 2 
3 4 

2 2 2 
69 69 
69 69 
*/

• 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