Submission #838079

#	Time	Username	Problem	Language	Result	Execution time	Memory
838079		caganyanmaz	Carnival Tickets (IOI20_tickets)	C++17	39 / 100	3057 ms	215080 KiB

tickets

#include <bits/stdc++.h>
#define pb push_back
#define mp(x...) array<int, 2>({x})
#define int int64_t
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int INF = 1e15;
constexpr static int MXN = 1505;
int prefix[MXN][MXN], suffix[MXN][MXN];
void allocate_tickets(vector<vector<int32_t>> s);

int find_maximum(int32_t _k, vector<vector<int32_t>> x) 
{
	int k = _k;
	int n = x.size();
	int m = x[0].size();
	vector<vector<array<int, 2>>> dp(n+1, vector<array<int,2>>((k*n/2)+1, mp(-INF, -1)));
	dp[0][0] = {0, -1};
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= m; j++)
			prefix[i][j] = prefix[i][j-1] + x[i][j-1];
		for (int j = m-1; j >= 0; j--)
			suffix[i][j] = suffix[i][j+1] + x[i][j];
		for (int j = 0; j <= k*n/2; j++)
		{
			for (int l = 0; l <= min(j, k); l++)
			{
				if (i == 0 && j == 2)
					debug(l, j-l, dp[i][j-l][0], prefix[i][l], suffix[i][l-k+m]);
				dp[i+1][j] = max(dp[i+1][j], mp(dp[i][j-l][0] - prefix[i][l] + suffix[i][l-k+m], l));
			}
		}
	}
	int current_count = k*n/2;
	vector<vector<int32_t>> s(n, vector<int32_t>(m,-1));
	vector<array<int, 2>> bounds; // Left right
	debug("a");
	debug(dp);
	vector<array<int, 2>> counts; // Small count, n
	for (int i = n-1; i >= 0; i--)
	{
		debug(i);
		int current_val = dp[i+1][current_count][1];
		debug(i, current_val);
		counts.pb({current_val, i});
		current_count -= current_val;
		debug(i, current_count);
		bounds.pb({0, m-1});
	}
	sort(counts.begin(), counts.end());
	for (int i = 0; i < k; i++)
	{
		for (int j = n/2; j < n; j++)
		{
			s[counts[j][1]][bounds[counts[j][1]][0]++] = i;
			counts[j][0]--;
		}
		for (int j = 0; j < n/2; j++)
		{
			s[counts[j][1]][bounds[counts[j][1]][1]--] = i;
		}
		sort(counts.begin(), counts.end());
	}
	debug("b");
	allocate_tickets(s);
	return dp[n][k*n/2][0];

}

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