Submission #1078237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078237		Tsovak	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	44 ms	5212 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];
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 dp0[N][N * M];

void maxu(ll& a, ll b) { a = max(a, b); }

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

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++) dp0[i][j] = -ll(1e18);

	dp0[0][0] = 0;

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

			for (int k = 0; k <= m; k++) {
				if (j + k <= n / 2 * m && i * m - j + (m - k) <= n / 2 * m)
					maxu(dp0[i + 1][j + k], dp0[i][j] - qry(i + 1, 0, k - 1) + qry(i + 1, k, m - 1));
			}
		}
	}

	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));
	assert(k < m || ans == dp0[n][n / 2 * m]);

	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:160:22: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |   assert(x[i].size() == m - k);
      |          ~~~~~~~~~~~~^~~~~~~~
tickets.cpp:108:9: warning: unused variable 'v' [-Wunused-variable]
  108 |  int u, v;
      |         ^

• 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