Submission #1017729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017729		ZeroCool	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	459 ms	76120 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define int long long

long long find_maximum(signed k, std::vector<std::vector<signed>> A) {
	
	int n = A.size();
	int m = A[0].size();
	
	vector<vector<signed> > res(n, vector<signed>(m, -1));
	int ans = 0;
	int cnt[n];
	priority_queue<ar<int, 2> > pq;
	for(int i = 0;i < n;i++){
		cnt[i] = k - 1;
		for(int j = 0;j < k;j++)ans -= A[i][j];
		pq.push({A[i][k-1] + A[i][m-1], i});
	}
	
	for(int it = 0;it < n * k / 2;it++){
		int x = pq.top()[0];
		int i = pq.top()[1];
		pq.pop();
		ans += x;
		--cnt[i];
		if(cnt[i] == -1)continue;
		
		pq.push({A[i][cnt[i]] + A[i][m - k + cnt[i]], i});
	}
	
	int r = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= cnt[i];j++)res[i][j] = (r++) % k;
		int t = r;
		for(int j = m - k + cnt[i] + 1;j < m;j++)res[i][j] = (t++) % k;
	}
	
	allocate_tickets(res);
	return ans;
}

#define int signed

Compilation message (stderr)

tickets.cpp:46: warning: "int" redefined
   46 | #define int signed
      | 
tickets.cpp:7: note: this is the location of the previous definition
    7 | #define int long long
      |

• 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