Submission #1014165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014165		0npata	Carnival Tickets (IOI20_tickets)	C++17	39 / 100	3104 ms	2097152 KiB

tickets

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

using namespace std;

#define vec vector
#define int long long

const int INF = 1e17;


long long find_maximum(int32_t k, vec<vec<int32_t>> x) {
	int n = x.size();
	int m = x[0].size();

	vec<vec<pair<int, int>>> dp(n+1, vec<pair<int, int>>(k*n+1, {-INF, -1}));
	dp[0][0] = {0, -1};
	vec<vec<int32_t>> ans(n, vec<int32_t>(m, -1));

	for(int i = 0; i<n; i++) {
		int cur = 0;
		for(int j = m-1; j >= m-k; j--) {
			cur += x[i][j];
		}
		for(int j = 0; j<=k; j++) {
			for(int l = 0; l<k*n+1; l++) {
				if(l+j >= k*n+1) {
					continue;
				}
				if(dp[i][l].first+cur > dp[i+1][l+j].first) {
					dp[i+1][l+j] = {dp[i][l].first+cur, j};
				}
			}

			cur -= x[i][j];
			cur -= x[i][m-k+j];
		}
	}

	vec<pair<vec<int>, int>> mxs(n);
	vec<pair<vec<int>, int>> mns(n);

	vec<int> mn_cnt_seq(n);
	int cur = k*n/2;
	for(int i = n; i>0; i--) {
		mn_cnt_seq[i-1] = dp[i][cur].second;
		assert(dp[i][cur].second != -1);
		cur -= dp[i][cur].second;
		assert(cur >= 0);
	}

	//cerr << "MN_CNT_SEQ: ";
	//for(int i = 0; i<n; i++) {
		//cerr << mn_cnt_seq[i] << ' ';
	//}
	//cerr << '\n';

	for(int i = 0; i<n; i++) {
		mns[i] = {{}, i};
		for(int j = 0; j<mn_cnt_seq[i]; j++) {
			mns[i].first.push_back(j);
		}
		mxs[i] = {{}, i};
		for(int j = m-1; j>=m-(k-mn_cnt_seq[i]); j--) {
			mxs[i].first.push_back(j);
		}
	}

	for(int i = 0; i<k; i++) {
		sort(mns.begin(), mns.end(), [](auto& el1, auto& el2) { return el1.first.size() > el2.first.size(); });
		sort(mxs.begin(), mxs.end(), [](auto& el1, auto& el2) { return el1.first.size() > el2.first.size(); });
		set<int> used;
		for(int j = 0; j<n/2; j++) {
			used.insert(mns[j].second);
			int l = mns[j].first.back();
			mns[j].first.pop_back();
			ans[mns[j].second][l] = i;
		}
		int cntmx = 0;
		for(int j = 0; j<n; j++) {
			if(used.count(mxs[j].second)) continue;
			assert(mxs[j].first.size() > 0);
			int l = mxs[j].first.back();
			mxs[j].first.pop_back();
			ans[mxs[j].second][l] = i;
		}
	}

	allocate_tickets(ans);

	return dp[n][k*n/2].first;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int32_t, std::vector<std::vector<int> >)':
tickets.cpp:79:7: warning: unused variable 'cntmx' [-Wunused-variable]
   79 |   int cntmx = 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