Submission #1078388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078388		Tsovak	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	10 ms	5980 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

// -------------------- Solution -------------------- //

const int N = 85, M = 85;
deque<int> x[N], pp[N];
int ul[N], ur[N];
int n, m, k;

ll dp[N][N * M];
int from[N][N * M];

ll qry(int i, int l, int r)
{
	if (l > r) return 0;
	if (l == 0) return pp[i][r];
	return pp[i][r] - pp[i][l - 1];
}

set<pr<int, int>> st1, st2;
deque<int> d1[N], d2[N];

multiset<int> st[N][N];

ll find_maximum(int k0, vector<vector<int>> x0)
{
	int i, j;

	n = x0.size();
	m = x0[0].size();
	k = k0;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < m; j++) {
			x[i].pb(x0[i - 1][j]);

			if (j == 0) pp[i].pb(x0[i - 1][j]);
			else pp[i].pb(pp[i].bk() + x0[i - 1][j]);
		}
	}

	vector<vector<int>> res(n, vector<int>(m, -1));
	ll ans = 0;


	for (i = 0; i <= n + 1; i++) for (j = 0; j <= n * m + 1; j++) dp[i][j] = -ll(1e18);

	dp[0][0] = 0;

	int lim = k * n / 2;

	for (i = 0; i < n; i++) {
		for (j = 0; j <= min(i * m, lim); j++) {
			if (dp[i][j] == -ll(1e18)) continue;

			for (int kk = 0; kk <= k; kk++) {
				if (j + kk <= lim && i * k - j + (k - kk) <= lim) {

					if (dp[i + 1][j + kk] < dp[i][j] - qry(i + 1, 0, kk - 1) + qry(i + 1, m - (k - kk), m - 1)) {
						dp[i + 1][j + kk] = dp[i][j] - qry(i + 1, 0, kk - 1) + qry(i + 1, m - (k - kk), m - 1);
						from[i + 1][j + kk] = kk;
					}
				}
			}
		}
	}

	//for (i = 0; i <= n; i++) for (j = 0; j <= lim; j++) cout << i << ' ' << j << ' ' << dp[i][j] << "\n";

	ans = dp[n][lim];

	j = lim;

	for (i = n; i >= 1; i--) {
		int e = from[i][j];

		ul[i] = e;
		ur[i] = k - e;

		j -= e;
	}


	/*for (i = 1; i <= n; i++) {
		cout << ul[i] << ' ' << ur[i] << "\n";

	}*/


	for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) for (int kk = 0; kk < k; kk++) st[i][j].insert(kk);

	for (i = 1; i <= n; i++) {
		if (ul[i]) {
			st1.insert(mpr(x0[i - 1][0], i));
			for (j = 0; j < ul[i]; j++) d1[i].pb(x0[i - 1][j]);
		}

		if (ur[i]) {
			st2.insert(mpr(x0[i - 1][m - ur[i]], i));
			for (j = m - ur[i]; j < m; j++) d2[i].pb(x0[i - 1][j]);
		}
	}

	for (int he = 0; he < lim; he++) {
		pr<int, int> u = *st1.begin();

		st1.erase(st1.begin());
		d1[u.ss].popf();
		if (!d1[u.ss].empty()) st1.insert(mpr(d1[u.ss].ft(), u.ss));


		auto it = st2.begin(); if ((*it).ss == u.ss) it++;
		pr<int, int> v = *it;

		st2.erase(it);
		d2[v.ss].popf();
		if (!d2[v.ss].empty()) st2.insert(mpr(d2[v.ss].ft(), v.ss));


		//cout << u.ff << ' ' << u.ss << ' ' << v.ff << ' ' << v.ss << "\n";

		if (st[u.ss][v.ss].empty()) assert(false);

		int de = *st[u.ss][v.ss].begin();

		i = lower_bound(all(x0[u.ss - 1]), u.ff) - x0[u.ss - 1].begin();
		j = lower_bound(all(x0[v.ss - 1]), v.ff) - x0[v.ss - 1].begin();

		res[u.ss - 1][i] = res[v.ss - 1][j] = de;


		for (i = 1; i <= n; i++) {
			st[u.ss][i].erase(de);
			st[i][u.ss].erase(de);

			st[v.ss][i].erase(de);
			st[i][v.ss].erase(de);
		}
	}

	allocate_tickets(res);

	return ans;
}

• 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