Submission #559861

#	Time	Username	Problem	Language	Result	Execution time	Memory
559861		AlperenT	Carnival Tickets (IOI20_tickets)	C++17	30 / 100	617 ms	73060 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

long long find_maximum(int k, vector<vector<int>> arr){
	int n = arr.size();
	int m = arr[0].size();

	vector ans(n, vector(m, -1));
	long long ansvalue = 0;

	int mx = 0;

	for(auto i : arr){
		for(auto j : i){
			mx = max(mx, j);
		}
	}

	if(mx <= 1){
		vector zeros(n, vector<int>()), ones(n, vector<int>());

		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(arr[i][j] == 0) zeros[i].push_back(j);
				else if(arr[i][j] == 1) ones[i].push_back(j);
			}
		}

		for(int i = 0; i < k; i++){
			vector<pair<int, int>> v;

			for(int j = 0; j < n; j++) v.push_back({zeros[j].size(), j});

			sort(v.begin(), v.end(), greater<decltype(v[0])>());

			int zerocnt = 0, onecnt = 0;

			for(int j = 0; j < n / 2; j++){
				if(!zeros[v[j].second].empty()){
					ans[v[j].second][zeros[v[j].second].back()] = i;
					zeros[v[j].second].pop_back();
					zerocnt++;
				}
				else{
					ans[v[j].second][ones[v[j].second].back()] = i;
					ones[v[j].second].pop_back();
					onecnt++;
				}
			}

			for(int j = n / 2; j < n; j++){
				if(!ones[v[j].second].empty()){
					ans[v[j].second][ones[v[j].second].back()] = i;
					ones[v[j].second].pop_back();
					onecnt++;
				}
				else{
					ans[v[j].second][zeros[v[j].second].back()] = i;
					zeros[v[j].second].pop_back();
					zerocnt++;
				}
			}

			ansvalue += min(n / 2, onecnt) - max(onecnt - n / 2, 0);
		}
	}
	else if(m == 1){
		vector<int> v;

		for(int i = 0; i < m; i++) v.push_back(arr[0][i]);

		sort(v.begin(), v.end());

		for(int i = 0; i < n / 2; i++) ansvalue -= v[i];
		for(int i = n / 2; i < n; i++) ansvalue += v[i];

		for(int i = 0; i < n; i++) ans[i][0] = 0;
	}
	else if(k == 1){
		vector<pair<int, int>> v;

		for(int i = 0; i < n; i++){
			ansvalue += arr[i][m - 1];
			v.push_back({arr[i][m - 1] + arr[i][0], i});
		}

		sort(v.begin(), v.end());

		for(int i = 0; i < n / 2; i++){
			ansvalue -= v[i].first;

			ans[v[i].second][0] = 0;
		}

		for(int i = n / 2; i < n; i++){
			ans[v[i].second][m - 1] = 0;
		}
	}
	else{ 
		// cry till I die
	}

	allocate_tickets(ans);
	return ansvalue;
}

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