oj.uz

Submission #1050644

# Submission time Handle Problem Language Result Execution time Memory
1050644 2024-08-09T12:05:06 Z mychecksedad Carnival Tickets (IOI20_tickets) C++17
76 / 100
 654 ms 85408 KB 
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(),x.end()

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(n, vector<int>(m, -1));

	vector<array<int, 3>> D;	
	vector<vector<vector<int>>> C(n, vector<vector<int>>(2));	
	ll ans = 0;
	for(int i = 0; i < n; ++i) for(int j = m - k; j < m; ++j) {
		ans += x[i][j];
		D.pb({-(x[i][j] + x[i][j - (m-k)]), i, j});
	}
	sort(all(D), greater<array<int,3>>());

	for(int i = 0; i < n*k; ++i){
		if(i < n*k/2){
			ans += D[i][0];
			C[D[i][1]][0].pb(D[i][2] - (m-k));
		}else{
			C[D[i][1]][1].pb(D[i][2]);
		}
	}
	for(int i = 0; i < n; ++i) sort(all(C[i][0]), greater<int>()), sort(all(C[i][1]));
	for(int i = 0; i < k; ++i){
		set<pair<int, int>> S;
		for(int i = 0; i < n; ++i){
			S.insert({C[i][1].size(), i});
		}
		int cur = 0;
		auto it = S.begin();
		vector<ll> tot;
		while(it != S.end()){
			int v =  (*it).second;
			if((cur < n/2 && C[v][0].size()) || (cur >= n/2 && C[v][1].size() == 0)){
				answer[v][C[v][0].back()] = i;
				C[v][0].pop_back();
			}else{
				answer[v][C[v][1].back()] = i;
				C[v][1].pop_back();
			}
			++cur;
			it = next(it);
		}
		// cout << "f" << endl;
	}

	allocate_tickets(answer);
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 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 348 KB Output is correct
5 Correct 15 ms 2396 KB Output is correct
6 Correct 317 ms 51584 KB Output is correct

Subtask #3
0 / 14.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 14 ms 3108 KB Output is correct
6 Correct 465 ms 64468 KB Output is correct
7 Correct 468 ms 70648 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 4 ms 1052 KB There is no ticket of color 26 on day 36
13 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 26 ms 3788 KB Output is correct
6 Correct 4 ms 884 KB Output is correct
7 Correct 5 ms 1296 KB Output is correct
8 Correct 645 ms 85408 KB Output is correct
9 Correct 620 ms 80540 KB Output is correct
10 Correct 639 ms 78748 KB Output is correct
11 Correct 654 ms 84816 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 11 ms 2392 KB Output is correct
14 Correct 12 ms 2396 KB Output is correct
15 Correct 17 ms 3028 KB Output is correct
16 Correct 23 ms 3792 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 704 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 23 ms 3288 KB Output is correct
21 Correct 18 ms 3028 KB Output is correct
22 Correct 25 ms 3528 KB Output is correct
23 Correct 21 ms 3632 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 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 348 KB Output is correct
11 Correct 15 ms 2396 KB Output is correct
12 Correct 317 ms 51584 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 14 ms 3108 KB Output is correct
18 Correct 465 ms 64468 KB Output is correct
19 Correct 468 ms 70648 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Incorrect 4 ms 1052 KB There is no ticket of color 26 on day 36
25 Halted 0 ms 0 KB -