oj.uz

Submission #1050642

# Submission time Handle Problem Language Result Execution time Memory
1050642 2024-08-09T12:04:40 Z mychecksedad Carnival Tickets (IOI20_tickets) C++17
76 / 100
 648 ms 85916 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])), sort(all(C[i][1]), greater<int>());
	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 0 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 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 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 11 ms 2472 KB Output is correct
6 Correct 292 ms 51596 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 3028 KB Output is correct
6 Correct 377 ms 66108 KB Output is correct
7 Correct 447 ms 72392 KB Output is correct
8 Correct 3 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 0
13 Halted 0 ms 0 KB -

Subtask #4
14.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 2 ms 604 KB Output is correct
5 Correct 26 ms 4048 KB Output is correct
6 Correct 3 ms 884 KB Output is correct
7 Correct 5 ms 1312 KB Output is correct
8 Correct 620 ms 85916 KB Output is correct
9 Correct 628 ms 81292 KB Output is correct
10 Correct 639 ms 79260 KB Output is correct
11 Correct 648 ms 84124 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 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 11 ms 2392 KB Output is correct
14 Correct 12 ms 2472 KB Output is correct
15 Correct 17 ms 3028 KB Output is correct
16 Correct 22 ms 3792 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 18 ms 3132 KB Output is correct
21 Correct 21 ms 3104 KB Output is correct
22 Correct 22 ms 3536 KB Output is correct
23 Correct 22 ms 3536 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 11 ms 2472 KB Output is correct
12 Correct 292 ms 51596 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 3028 KB Output is correct
18 Correct 377 ms 66108 KB Output is correct
19 Correct 447 ms 72392 KB Output is correct
20 Correct 3 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 0
25 Halted 0 ms 0 KB -