oj.uz

Submission #425162

# Submission time Handle Problem Language Result Execution time Memory
425162 2021-06-12T14:18:15 Z Mlxa Carnival Tickets (IOI20_tickets) C++14
25 / 100
 657 ms 63372 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "tickets.h"
#include <vector>

const int N = 2000;
int cnt[N], lef[N], rig[N];

ll find_maximum(int k, vector<vector<int>> x) {
	int n = (int)x.size();
	int m = (int)x[0].size();
	
	vector<vector<int>> answer(n, vector<int>(m, -1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cnt[i] += x[i][j];
		}
	}
	fill_n(lef, n, 0);
	fill_n(rig, n, m - 1);

	vector<int> rows(n);
	iota(all(rows), 0);
	for (int i = 0; i < k; ++i) {
		sort(all(rows), [&](int ii, int jj) {
			return cnt[ii] < cnt[jj];
		});
		// cout << "--- " << i << endl;
		for (int j = 0; j < n / 2; ++j) {
			int sj = j;
			j = rows[j];
			// cout << "lef " << j << endl;
			cnt[j] -= x[j][lef[j]];
			answer[j][lef[j]++] = i;
			j = sj;
		}
		for (int j = n / 2; j < n; ++j) {
			int sj = j;
			j = rows[j];
			// cout << "rig " << j << endl;
			cnt[j] -= x[j][rig[j]];
			answer[j][rig[j]--] = i;
			j = sj;
		}
	}

	vector<vector<int>> res(k);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			// cout << answer[i][j] << " ";
			if (answer[i][j] != -1) {
				res[answer[i][j]].push_back(x[i][j]);
			}
		}
		// cout << endl;
	}
	ll sum = 0;
	for (int i = 0; i < k; ++i) {
		sort(all(res[i]));
		assert((int)res[i].size() == n);
		for (int j = 0; j < n / 2; ++j) {
			sum += res[i][n - 1 - j] - res[i][j];
		}
	}
	allocate_tickets(answer);
	return sum;
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Contestant returned 2444669794 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 24 ms 2712 KB Output is correct
6 Correct 657 ms 58512 KB Output is correct
7 Correct 612 ms 61148 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 844 KB Output is correct
13 Correct 20 ms 2172 KB Output is correct
14 Correct 21 ms 2420 KB Output is correct
15 Correct 626 ms 63372 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Contestant returned 24037843666 while correct return value is 24057831018.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 2 ms 332 KB Contestant returned 38716776456 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 2 ms 332 KB Contestant returned 38716776456 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Contestant returned 2444669794 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -