제출 #301093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301093		gs14004	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	349 ms	260172 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);
}

lint dp[1500][10000];
int track[1500][10000];

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;
	fill(dp[0] + 1, dp[0] + 10000, -1e18);
	for(int i=0; i<n; i++){
		fill(dp[i + 1], dp[i + 1] + 10000, -1e18);
		lint sum = 0;
		for(int j=0; j<k; j++){
			sum -= x[i][j];
		}
		for(int j = 0; j <= k; j++){
			for(int x = j; x <= (i + 1) * k; x++){
				if(dp[i + 1][x] < dp[i][x - j] + sum){
					dp[i + 1][x] = dp[i][x - j] + sum;
					track[i + 1][x] = j;
				}
			}
			sum += x[i][m - 1 - j];
			if(j != k) sum += x[i][k - 1 - j];
		}
	}
	int fuck = (n / 2) * k;
	for(int i = n; i; i--){
		int nxt = track[i][fuck];
		fuck -= nxt;
		for(int j = 0; j < nxt; j++) B[i-1][j] = -1;
		nxt = k - nxt;
		for(int j = m - nxt; j < m; j++) B[i-1][j] = +1;
	}
	/*
	sort(all(v));
	int l = 0, r = sz(v) - 1;
	vector<int> cnt(n);
	lint ret = 0;
	for(int i=0; i<(n/2)*k; i++){
		while(cnt[v[l].x] == k) l++;
		B[v[l].x][v[l].y] = -1;
		ret -= v[l].v;
		cnt[v[l].x]++;
		l++;
		while(cnt[v[r].x] == k) r--;
		B[v[r].x][v[r].y] = 1;
		ret += v[r].v;
		cnt[v[r].x]++;
		r--;
	}*/
	FUCKING_BACKTRACK(B, k);
	return dp[n][(n/2)*k];
}

• Subtask 1: 0 / 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