oj.uz

Submission #1050657

# Submission time Handle Problem Language Result Execution time Memory
1050657 2024-08-09T12:12:11 Z mychecksedad Carnival Tickets (IOI20_tickets) C++17
76 / 100
 674 ms 85508 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>>());

	int co = 0;

	for(int i = 0; i < n*k; ++i){
		if(co < n*k/2 && answer[D[i][1]][D[i][2] - (m-k)] == -1){
			ans += D[i][0];
			C[D[i][1]][0].pb(D[i][2] - (m-k));
			answer[D[i][1]][D[i][2] - (m-k)] = 1;
			++co;
		}else{
			C[D[i][1]][1].pb(D[i][2]);
			answer[D[i][1]][D[i][2]] = 1;
		}
	}
	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 j = 0; j < n; ++j){
			assert(C[j][0].size() || C[j][1].size());
			S.insert({C[j][1].size(), j});
		}
		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 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 0 ms 348 KB Output is correct
5 Correct 0 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 13 ms 2424 KB Output is correct
6 Correct 275 ms 51712 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 16 ms 3024 KB Output is correct
6 Correct 394 ms 64672 KB Output is correct
7 Correct 459 ms 72096 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 720 KB Output is correct
5 Correct 27 ms 3792 KB Output is correct
6 Correct 4 ms 880 KB Output is correct
7 Correct 6 ms 1312 KB Output is correct
8 Correct 650 ms 85508 KB Output is correct
9 Correct 654 ms 80032 KB Output is correct
10 Correct 642 ms 78488 KB Output is correct
11 Correct 674 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 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 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 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 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 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 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 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 11 ms 2648 KB Output is correct
14 Correct 12 ms 2396 KB Output is correct
15 Correct 16 ms 3124 KB Output is correct
16 Correct 23 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 3288 KB Output is correct
21 Correct 19 ms 3024 KB Output is correct
22 Correct 24 ms 3536 KB Output is correct
23 Correct 22 ms 3532 KB Output is correct

Subtask #7
0 / 10.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 0 ms 348 KB Output is correct
5 Correct 0 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 13 ms 2424 KB Output is correct
12 Correct 275 ms 51712 KB Output is correct
13 Correct 0 ms 344 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 16 ms 3024 KB Output is correct
18 Correct 394 ms 64672 KB Output is correct
19 Correct 459 ms 72096 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 -