oj.uz

Submission #849516

# Submission time Handle Problem Language Result Execution time Memory
849516 2023-09-14T23:00:51 Z IBory Carnival Tickets (IOI20_tickets) C++17
27 / 100
 387 ms 52816 KB 
#include "tickets.h"
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 1505;
int L[MAX], R[MAX];

ll find_maximum(int K, vector<vector<int>> X) {
	int N = X.size();
	int M = X[0].size();
	ll ans = 0;
	vector<vector<int>> used;
	for (int i = 0; i < N; ++i) {
		vector<int> go(M, -1);
		used.push_back(go);
	}

	fill(L, L + N, 0);
	fill(R, R + N, M - 1);
	for (int k = 0; k < K; ++k) {
		vector<pii> T;
		ll init = 0;
		for (int i = 0; i < N; ++i) {
			init += X[i][R[i]];
			T.emplace_back(-X[i][L[i]] - X[i][R[i]], i);
		}
		sort(T.begin(), T.end(), greater<pii>());
		for (int i = 0; i < N / 2; ++i) {
			auto [v, id] = T[i];
			init += v;
			used[id][L[id]++] = k;
		}
		for (int i = N / 2; i < N; ++i) {
			auto [_, id] = T[i];
			used[id][R[id]--] = k;
		}
		ans += init;
	}

	allocate_tickets(used);
	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 600 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 344 KB Output is correct
5 Correct 16 ms 2456 KB Output is correct
6 Correct 377 ms 51516 KB Output is correct

Subtask #3
0 / 14.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 2 ms 344 KB Output is correct
5 Correct 17 ms 2396 KB Output is correct
6 Correct 356 ms 52564 KB Output is correct
7 Correct 387 ms 52816 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Contestant returned 43 while correct return value is 45.
11 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 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 348 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 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 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 16 ms 2456 KB Output is correct
12 Correct 377 ms 51516 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 2 ms 344 KB Output is correct
17 Correct 17 ms 2396 KB Output is correct
18 Correct 356 ms 52564 KB Output is correct
19 Correct 387 ms 52816 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Incorrect 1 ms 348 KB Contestant returned 43 while correct return value is 45.
23 Halted 0 ms 0 KB -