Submission #1078127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078127		Tsovak	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	2476 ms	103324 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 = 1505, M = 1505;
deque<int> x[N];
int ul[N], ur[N];
int n, m;

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

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

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

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

	if (m == 1) {
		sort(x + 1, x + n + 1);

		for (i = 1; i <= n / 2;i++) ans -= x[i][0];
		for (i = n - n / 2 + 1; i <= n; i++) ans += x[i][0];

		for (i = 0; i < n; i++) res[i][0] = 0;

		allocate_tickets(res);

		return ans;
	}


	int u, v;

	for (i = 1; i <= n; i++) {
		ul[i] = 0;
		ur[i] = m - 1;
	}

	for (int kk = 0; kk < k; kk++) {

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

		dp[0][0] = 0;

		for (i = 0; i < n; i++) {
			for (j = 0; j <= min(i, n / 2); j++) {

				if (dp[i][j] != -ll(1e18)) {
					if (j < n / 2 && dp[i + 1][j + 1] < dp[i][j] - x[i + 1].ft()) {
						dp[i + 1][j + 1] = dp[i][j] - x[i + 1].ft();
						from[i + 1][j + 1] = j;
					}

					if (i - j < n / 2 && dp[i + 1][j] < dp[i][j] + x[i + 1].bk()) {
						dp[i + 1][j] = dp[i][j] + x[i + 1].bk();
						from[i + 1][j] = j;
					}
				}
			}
		}


		ans += dp[n][n / 2];

		u = n / 2;

		for (i = n; i >= 1; i--) {
			if (from[i][u] != u) {
				res[i - 1][ul[i]] = kk;
				ul[i]++;
				x[i].popf();
			}
			else {
				res[i - 1][ur[i]] = kk;
				ur[i]--;
				x[i].popb();
			}

			u = from[i][u];
		}
	}

	allocate_tickets(res);

	return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:59:9: warning: unused variable 'v' [-Wunused-variable]
   59 |  int u, v;
      |         ^

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