oj.uz

Submission #787084

# Submission time Handle Problem Language Result Execution time Memory
787084 2023-07-18T19:28:41 Z Pablo_No Carnival Tickets (IOI20_tickets) C++17
27 / 100
 351 ms 51832 KB 
#include "tickets.h"
#include <vector>
#include <queue>
#include <set>
	
using namespace std;
	
#define int long long
	
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
	int n = x.size();
	int m = x[0].size();
	
	std::vector<std::vector<signed>> ans(n, vector<signed>(m, -1));
	long long ansv = 0;

	priority_queue<pair<int, pair<int, int>>> pq;

	set<pair<int, int>> anss, anss2;
	
	for(int j = 0; j < n; j++)
	{
		for(int i = 0; i < k; i++)
		{
			ansv += x[j][m-1-i];
			anss.insert({m-1-i, -j});
		}

		pq.push({-x[j][0]-x[j][m-k], {j, 0}});
	}

	int ac = k*n/2;

	while(ac--)
	{
		auto ss = pq.top();
		pq.pop();

		anss2.insert({ss.second.second, ss.second.first});
		anss.erase({m-k+ss.second.second, -ss.second.first});

		ansv += ss.first;

		if(ss.second.second < k-1)
			pq.push({-x[ss.second.first][ss.second.second+1]-x[ss.second.first][m-k+(ss.second.second+1)], {ss.second.first, ss.second.second+1}});
	}

	int tim = 0;

	for(auto vv : anss)
	{
		ans[-vv.second][vv.first] = tim/(n/2);
		tim++;
	}

	tim = 0;

	for(auto vv : anss2)
	{
		ans[vv.second][vv.first] = tim/(n/2);
		tim++;
	}

	
	allocate_tickets(ans);
	return ansv;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 812 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 16 ms 2608 KB Output is correct
6 Correct 351 ms 51832 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB There is multiple tickets of color 1 on day 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 812 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 284 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 16 ms 2608 KB Output is correct
12 Correct 351 ms 51832 KB Output is correct
13 Incorrect 1 ms 212 KB There is multiple tickets of color 1 on day 0
14 Halted 0 ms 0 KB -