Submission #301070

#	Time	Username	Problem	Language	Result	Execution time	Memory
301070		gs14004	카니발 티켓 (IOI20_tickets)	C++17	25 / 100	1303 ms	88892 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 1505;

struct node{
	int x, y, v;
	bool operator<(const node &n)const{
		return v < n.v;
	}
};

void FUCKING_BACKTRACK(vector<vector<int>> B, int k){
	deque<int> dq[MAXN];
	int bcnt[MAXN] = {};
	for(int i=0; i<sz(B); i++){
		for(auto &j : B[i]){
			if(j > 0) bcnt[i]++;
		}
		for(int j=0; j<sz(B[i]); j++){
			if(B[i][j] == -1) dq[i].push_back(j);
		}
		for(int j=0; j<sz(B[i]); j++){
			if(B[i][j] == +1) dq[i].push_back(j);
		}
		for(int j=0; j<sz(B[i]); j++){
			if(B[i][j] == 0) B[i][j] = -1;
			else B[i][j] = 0;
		}
	}
	for(int i = 0; i < k; i++){
		vector<int> idx(sz(B));
		iota(all(idx), 0);
		sort(all(idx), [&](const int &a, const int &b){
			return bcnt[a] < bcnt[b];
		});
		for(int j=0; j<sz(B); j++){
			int x = idx[j];
			int y = (j < sz(B) / 2 ? dq[x].front() : dq[x].back());
			B[x][y] = i;
			if(j < sz(B) / 2) dq[x].pop_front();
			else{
				dq[x].pop_back();
				bcnt[x]--;
			}
		}
	}
	allocate_tickets(B);
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = sz(x);
	int m = sz(x[0]);
	vector<vector<int>> B(n);
	for(auto &i : B) i.resize(m);
	vector<node> v;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			v.push_back({i, j, x[i][j]});
		}
	}
	sort(all(v));
	lint ret = 0;
	for(int i=0; i<(n/2)*k; i++){
		B[v[i].x][v[i].y] = -1;
		ret -= v[i].v;
	}
	for(int i=n*m-(n/2)*k; i<n*m; i++){
		B[v[i].x][v[i].y] = +1;
		ret += v[i].v;
	}
	FUCKING_BACKTRACK(B, k);
	return ret;
}

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