oj.uz

Submission #489726

# Submission time Handle Problem Language Result Execution time Memory
489726 2021-11-24T04:28:00 Z 8e7 Carnival Tickets (IOI20_tickets) C++17
0 / 100
 1 ms 204 KB 
#include "tickets.h"
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1505
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;
ll cost[maxn][maxn];
int pref[maxn], suf[maxn];
priority_queue<pii, vector<pii>, less<pii> > pq;
long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	ll tot = 0, small = 0;
	for (int i = 0;i < n;i++) {
		for (int j = m - k;j < m;j++) {
			tot += x[i][j];
			cost[i][j - m + k] = -x[i][j - m + k] - x[i][j];
		}	
		for (int j = 1;j <= k;j++) cost[i][j] += cost[i][j-1];
		//pary(cost[i], cost[i] + k + 1);
	}
	vector<vector<int> > ans(n, vector<int>(m, -1));
	for (int i = 0;i < n;i++) {
		pref[i] = 0, suf[i] = m - k;
		pq.push({cost[i][0], i});
	}
	for (int ti = 0;ti < n * k / 2;ti++) {
		pii best = pq.top();pq.pop();
		int i = best.ss;
		pref[i]++, suf[i]++;
		small += best.ff;
		if (pref[i] < k) pq.push({cost[i][pref[i]], i});
	}
	
	int ord[n];
	for (int i = 0;i < n;i++) ord[i] = i;
	for (int ti = 0;ti < k;ti++) {
		sort(ord, ord + n, [&](int x, int y){return pref[x] > pref[y];});
		int rem = n / 2;
		for (int j = 0;j < n;j++) {
			int i = ord[j];
			if (pref[i] && rem) {
				rem--;
				pref[i]--;
				ans[i][pref[i]] = ti;
			} else {
				ans[i][suf[i]] = ti;
				suf[i]++;
			}
		}
	}	
	allocate_tickets(ans);
	debug(tot, small);
	return tot + small;
}
/*
2 3 2
0 2 5
1 1 3


4 2 1
5 9
1 4
3 6
2 7
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB secret mismatch
2 Halted 0 ms 0 KB -