Submission #416474

#	Time	Username	Problem	Language	Result	Execution time	Memory
416474		Kevin_Zhang_TW	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	807 ms	76100 KiB

tickets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV 
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "tickets.h"
#include <vector>

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

	ll sum = 0;
	vector<int> lat(n), rat(n, m);

	for (int i = 0;i < n;++i) {
		for (int j = 0, &ind = rat[i];j < k;++j)
			sum += x[i][--ind];
	}

	int req = n / 2 * k;

	priority_queue< pair<ll,ll> > pq;

	auto upd = [&](int ind) {
		pq.emplace( -(x[ind][lat[ind]] + x[ind][rat[ind]]), ind );
	};

	for (int i = 0;i < n;++i)
		upd(i);

	while (req--) {
		auto [ w, id ] = pq.top(); pq.pop();
		sum += w;

		DE(id, lat[id], rat[id]);
		++lat[id], ++rat[id];
		if (lat[id] == k) continue;
		upd(id);
	}

	vector<vector<int>> answer(n, vector<int>(m, -1));

	for (int i = 0, s = 0;i < n;++i) {

		DE(i, lat[i], rat[i]);

		int c = s;

		for (int j = 0;j < lat[i];++j) {
			answer[i][j] = c++;
			if (c == k) c = 0;
		}
		for (int j = rat[i];j < m;++j) {
			answer[i][j] = c++;
			if (c == k) c = 0;
		}

		s = (s + lat[i]) % k;
	}

	allocate_tickets(answer);
	return sum;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tickets.cpp:47:3: note: in expansion of macro 'DE'
   47 |   DE(id, lat[id], rat[id]);
      |   ^~
tickets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tickets.cpp:57:3: note: in expansion of macro 'DE'
   57 |   DE(i, lat[i], rat[i]);
      |   ^~

• 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