Submission #1078169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078169		Tsovak	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	2840 ms	108420 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, k;

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

ll calc(vector<vector<int>> res)
{
	int i, j;

	vector<vector<int>> ve(k);

	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (res[i][j] == -1) continue;

			ve[res[i][j]].pb(x[i + 1][j]);
		}
	}

	ll ans = 0;

	for (i = 0; i < k; i++) {
		assert(ve[i].size() == n);

		sort(all(ve[i]));

		for (j = 0; j < n / 2; j++) ans -= ve[i][j];
		for (j = n - n / 2; j < n; j++) ans += ve[i][j];
	}

	return ans;
}

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]);

	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];
		}
	}

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

	assert(ans == calc(res));

	allocate_tickets(res);

	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from tickets.cpp:2:
tickets.cpp: In function 'll calc(std::vector<std::vector<int> >)':
tickets.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   assert(ve[i].size() == n);
      |          ~~~~~~~~~~~~~^~~~
tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:140:22: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |   assert(x[i].size() == m - k);
      |          ~~~~~~~~~~~~^~~~~~~~
tickets.cpp:88:9: warning: unused variable 'v' [-Wunused-variable]
   88 |  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