oj.uz

Submission #300206

# Submission time Handle Problem Language Result Execution time Memory
300206 2020-09-17T00:59:33 Z sjimed Carnival Tickets (IOI20_tickets) C++14
0 / 100
 1 ms 384 KB 
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf = 1e9;
const ll INF = 1e18;

vector<int> l[1510];
vector<int> s[1510];

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>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m, 0);
		answer.push_back(row);
	}

	ll ret = 0;
	int cnt[1510] = {};
	priority_queue<pii> pq;
	for(int i=0; i<n; i++) {
		for(int j=0; j<k; j++) {
			ret -= x[i][j];
			answer[i][j] = -1;
		}
		cnt[i] = k;
		pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]] , i);
	}

	int T = n/2 * k;

	while(T--) {
		int i = pq.top().se;
		ret += pq.top().fi;
		
		answer[i][cnt[i]-1] = 0;
		answer[i][m - 1 - k + cnt[i]] = 1;
		cnt[i]--;
		pq.pop();

		if(cnt[i]) pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]] , i);
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(answer[i][j] == 1) l[i].eb(j);
			else if(answer[i][j] == -1) s[i].eb(j);

			answer[i][j] = -1;
		}
	}

	for(int i=0; i<k; i++) {
		vector<int> t;
		for(int j=0; j<n; j++) t.eb(j);

		sort(all(t), [&] (int a, int b) {
			return l[a].size() < l[b].size();
		});

		for(int j=0; j<n/2; j++) {
			answer[t.back()][l[t.back()].back()] = i;
			l[t.back()].pop_back();
		}

		sort(all(t), [&] (int a, int b) {
			return s[a].size() < s[b].size();
		});

		for(int j=0; j<n/2; j++) {
			answer[t.back()][s[t.back()].back()] = i;
			s[t.back()].pop_back();
			t.pop_back();
		}
	}

	allocate_tickets(answer);
	return ret;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB There is no ticket of color 2 on day 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB There is no ticket of color 0 on day 0
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB There is no ticket of color 0 on day 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB There is no ticket of color 1 on day 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB There is no ticket of color 1 on day 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB There is no ticket of color 1 on day 1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB There is no ticket of color 2 on day 0
3 Halted 0 ms 0 KB -