Submission #1014323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014323		aykhn	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	340 ms	90588 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F

long long find_maximum(int k, vector<vector<int>> x) {
	assert(k == 1);
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n, vector<int> (m, -1));
	vector<vector<long long>> dp(n, vector<long long> (n / 2 + 5, -inf)), par(n, vector<long long> (n / 2 + 5, -1));
	dp[0][0] = -x[0][0], dp[0][1] = x[0][m - 1];
	par[0][0] = 0, par[0][1] = 0;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= n / 2; j++)
		{
			if (j)
			{
				if (dp[i - 1][j] - x[i][0] > dp[i - 1][j - 1] + x[i][m - 1])
				{
					dp[i][j] = dp[i - 1][j] - x[i][0];
					par[i][j] = j;
				}
				else 
				{
					dp[i][j] = dp[i - 1][j - 1] + x[i][m - 1];
					par[i][j] = j - 1;
				}
			}
			else
			{
				dp[i][j] = dp[i - 1][j] - x[i][0];
				par[i][j] = j;
			}
		}
	}
	int i = n - 1, j = n / 2;
	while (i >= 0)
	{
		if (par[i][j] == j) answer[i][0] = 0;
		else if (par[i][j] == j - 1) answer[i][m - 1] = 0;
		else assert(0);
		j = par[i][j];
		i--;
	}
	allocate_tickets(answer);
	return dp[n - 1][n / 2];
}

• 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