oj.uz

Submission #1050414

# Submission time Handle Problem Language Result Execution time Memory
1050414 2024-08-09T09:16:00 Z MercubytheFirst Carnival Tickets (IOI20_tickets) C++17
27 / 100
 286 ms 88912 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;


long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
	ll n = x.size();
	ll m = x[0].size();
	vector<vector<signed> > answer(n, vector<signed>(m, -1));
	vector<deque<pair<ll, ll> > > nums(n);
	for(ll i = 0; i < n; ++i) {
		for(ll j = 0; j < m; ++j) {
			nums[i].push_back({x[i][j], j});
		}
	}
	ll totalsum = 0;
	for(ll round = 0; round < k; ++round) {
		vector<pii> sums(n);
		for(ll i = 0; i < n; ++i) {
			sums[i] = {nums[i].front().first + nums[i].back().first, i};
		}
		sort(sums.begin(), sums.end());
		for(ll i = 0; i < n/2; ++i) {
			const ll idx1 = sums[i].second;
			const ll idx2 = nums[idx1].front().second;
			totalsum -= nums[idx1].front().first;
			answer[idx1][idx2] = round;
			nums[idx1].pop_front();
		}
		for(ll i = n/2; i < n; ++i) {
			const ll idx1 = sums[i].second;
			const ll idx2 = nums[idx1].back().second;
			totalsum += nums[idx1].back().first;
			answer[idx1][idx2] = round;
			nums[idx1].pop_back();
		}
	}
	allocate_tickets(answer);
	return totalsum;
}


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

2 3 2
0 2 5
1 1 3
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 12 ms 4008 KB Output is correct
6 Correct 286 ms 88912 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 5 while correct return value is 6.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 12 ms 4008 KB Output is correct
12 Correct 286 ms 88912 KB Output is correct
13 Incorrect 0 ms 348 KB Contestant returned 5 while correct return value is 6.
14 Halted 0 ms 0 KB -