Submission #313705

#	Time	Username	Problem	Language	Result	Execution time	Memory
313705		egorlifar	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1002 ms	84072 KiB

tickets

#include "tickets.h"
#include <vector>
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;


long long find_maximum(int k, vector<vector<int>> x) {
	int n = sz(x);
	int m = sz(x[0]);
	vector<vector<int> > res(n, vector<int>(m, -1));
	vector<int> h(n, 0), l(n, k);
	long long sum = 0;
	vector<pair<int, int> > st;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			st.emplace_back(x[i][k - j - 1] + x[i][m - j - 1], i);
			sum -= x[i][j];
		}
	}
	sort(rall(st));
	for (int i = 0; i < n * k / 2; i++) {
		sum += st[i].first;
		h[st[i].second]++;
		l[st[i].second]--;
	}
	for (int col = 0; col < k; col++) {
		int U = n / 2, L = n / 2;
		vector<bool> bad(n, false);
		for(int i = 0; i < n; i++) {
			if (h[i] == 0) {
				l[i]--;
				res[i][l[i]] = col;
				bad[i] = true;
				L--;
			} else if (l[i] == 0) {
				h[i]--;
				res[i][m - h[i] - 1] = col;
				bad[i] = true;
				U--;
			}
		}
		for (int i = 0; i < n; i++) {
			if (!bad[i]) {
				if (U) {
					h[i]--;
					res[i][m - h[i] - 1] = col;
					bad[i] = true;
					U--;
				} else {
					l[i]--;
					res[i][l[i]] = col;
					bad[i] = true;
					L--;
				}
			}
		}
	}
	allocate_tickets(res);
	return sum;
}

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