Submission #833818

#	Time	Username	Problem	Language	Result	Execution time	Memory
833818		gesgha	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1006 ms	104352 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
 
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
 
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector <T>;
 
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
 
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
 
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e6 + 10;
const int M = 3e3 + 100;
const int mod = 1e9 + 7;

ll dp[M][M];
int p[M][M];

int cnt[M][2];
ve <int> ones[M];
ve <int> zero[M];
set <int> can[M];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ve <ve <int>> A = x;
	set <pair <int, int>> ST;
	for (int i = 0; i < n; i++) ST.insert({cnt[i][1], i});

	ve <int> used(n, 0);
	ll ans = 0;
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) row[j] = -1;	
		answer.push_back(row);
	}
	ve <array <int, 3>> V;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			V.pb({x[i][j] + x[i][m - k + j], i, j});
		}
		for (int j = m - k; j < m; j++) ans += x[i][j];
	}
	sort(all(V));
	set <pii> cnt;
	ve <int> need(n, 0);
	ve  <ve <int>> have(n);
	for (int i = 0; i < k; i++) cnt.insert({0, i});
	for (int i = 0; i < k * n / 2; i++) {
		ans -= V[i][0];
		need[V[i][1]]++;
		have[V[i][1]].pb(V[i][2]);
	}
	for (int i = 0; i < n; i++) {
		int nd = need[i];
		ve <pii> Z;
		while(sz(Z) < nd) {
			auto [x, id] = *cnt.begin();
			cnt.erase(cnt.begin());
			Z.pb({x + 1, id});
		}
		fe (x, Z) {
			cnt.insert(x);
			answer[i][have[i].back()] = x.se;
			have[i].pop_back();
		}
	}
	for (int i = 0; i < n; i++) {
		set <int> can;
		for (int j = 0; j < k; j++) can.insert(j);
		for (int j = 0; j < m; j++) {
			if (answer[i][j] != -1) can.erase(answer[i][j]);
		}
		
		for (int j = m - 1; j >= 0; j--) {
			if (!sz(can)) break;
			answer[i][j] = *can.begin();
			can.erase(can.begin());
		}
	}

	allocate_tickets(answer);
	return ans;
}

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