Submission #1178064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178064		browntoad	Carnival Tickets (IOI20_tickets)	C++20	0 / 100	293 ms	8772 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define pip pair<int, pii> 
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())


void make_tickets(vector<vector<int>> nids, vector<vector<int>> pids, int k, int m){
	int n = SZ(nids);
	vector<vector<int>> ans(n);
	REP(i, n){
		ans[i] = vector<int> (m);
		REP(j, m) ans[i][j] = -1;
	}

	REP(t, k){
		vector<bool> tmp(n);
		int cnt = 0;
		REP(i, n) {
			if (cnt >= n/2) break;
			if (SZ(nids[i]) == 0){
				ans[i][pids[i].back()] = t;
				pids[i].pop_back();
				cnt++;
				tmp[i] = 1;
			}
		}
		REP(i, n){
			if (cnt >= n/2) break;
			if (SZ(pids[i]) > 0 && !tmp[i]){
				ans[i][pids[i].back()] = t;
				pids[i].pop_back();
				cnt++;
				tmp[i] = 1;
			}
		}
		REP(i, n){
			if (!tmp[i]){
				ans[i][nids[i].back()] = t;
				nids[i].pop_back();
			}
		}
	}
	allocate_tickets(ans);
}

const ll maxn = 85;

static ll dp[maxn][maxn*maxn];
static int pre[maxn][maxn*maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> tick(n); // -1 if neg, +1 if pos, 0 if nothing
	REP(i, n) tick[i] = vector<int> (m);

	ll sm = 0;
	REP(i, n){
		REP(j, k){
			sm -= x[i][j];
		}
	}

	REP(i, n){
		REP(j, n*k/2+1){ // currently how many plus conversions
			dp[i+1][j] = dp[i][j]; // take all negative here
			pre[i+1][j] = 0; // means how many i take from i

			ll cst = 0;
			REP1(l, k){
				if (j-l < 0) break;
				cst += x[i][m-l] + x[i][k-l];
				if (dp[i][j-l] + cst > dp[i+1][j]){
					dp[i+1][j] = dp[i][j-l] + cst;
					pre[i+1][j] = l;
				} 
			}
		}
	}

	int pus = n*k/2;
	int fans = dp[n][n*k/2] + sm;
	RREP(i, n){
		int tmp = pre[i+1][pus];
		REP(j, k-tmp) tick[i][j] = -1;
		REP(j, tmp) tick[i][m-j-1] = 1;
		pus -= tmp;
	}

	vector<vector<int>> poo1(n), poo2(n);
	REP(i, n){
		vector<int> t1, t2;
		REP(j, m){
			if (tick[i][j] == -1) t1.pb(j);
			if (tick[i][j] == 1) t2.pb(j);
		}
		poo1[i] = t1; poo2[i] = t2;
	}
	make_tickets(poo1, poo2, k, m);
	return fans;
}
/*
2 3 2
0 2 5
1 1 3
*/

• 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