oj.uz

답안 #416571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416571 2021-06-02T16:06:56 Z SuhaibSawalha1 카니발 티켓 (IOI20_tickets) C++17
41 / 100
 694 ms 70724 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
 
long long calc (vector<long long> &a) {
	int n = a.size();
	long long sum = accumulate(a.begin(), a.end(), 0LL), m = LLONG_MAX, sum2 = 0;
	sort(a.begin(), a.end());
	for (int i = 0; i < n; ++i) {
		sum -= a[i];
		m = min(m, a[i] * i - sum2 + sum - a[i] * (n - i - 1));
		sum2 += a[i];
	}
	return m;
}
 
long long find_maximum(int k, vector<vector<int>> a) {
	long long ans = 0;
	int n = a.size();
	int m = a[0].size();
	vector<vector<int>> g(n, vector<int>(m, -1));
	if (m == 1) {
		vector<long long> ask;
		g.assign(n, vector<int>(m, 0));
		for (auto &e : a) {
			ask.push_back(e[0]);
		}
		allocate_tickets(g);
		return calc(ask);
	}
	if (k == 1) {
		vector<vector<array<int, 2>>> a2(n, vector<array<int, 2>>(m));
		long long mxs = 0;
		vector<long long> ask;
		vector<array<int, 2>> ms;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				a2[i][j] = {a[i][j], j};
			}
			sort(a2[i].begin(), a2[i].end());
			mxs += a2[i][m - 1][0];
			ms.push_back({-a2[i][0][0] - a2[i][m - 1][0], i});
		}
		sort(ms.rbegin(), ms.rend());
		for (int i = 0; i < n / 2; ++i) {
			ask.push_back(a2[ms[i][1]][0][0]);
			g[ms[i][1]][a2[ms[i][1]][0][1]] = 0;
		}
		for (int i = 0; i < n; ++i) {
			if (count(g[i].begin(), g[i].end(), -1) == m) {
				ask.push_back(a2[i][m - 1][0]);
				g[i][a2[i][m - 1][1]] = 0;
			}
		}
		allocate_tickets(g);
		return calc(ask);
	}
	vector<pair<int, array<vector<int>, 2>>> t;
	for (int i = 0; i < n; ++i) {
		array<vector<int>, 2> v;
		for (int j = 0; j < m; ++j) {
			v[a[i][j]].push_back(j);
		}
		t.push_back({i, v});
	} 
	#define zero(a) a.second[0].size()
	#define one(a) a.second[1].size()
	for (int kc = 0; kc < k; ++kc) {
		sort(t.begin(), t.end(), [&] (auto &a, auto &b) {
			return zero(a) > zero(b);
		});
		int zeros = 0, ones = 0;
		for (int i = 0; i < n / 2; ++i) {
			if (zero(t[i])) {
				++zeros;
				g[t[i].first][t[i].second[0].back()] = kc;
				t[i].second[0].pop_back();
			}
			else {
				++ones;
				g[t[i].first][t[i].second[1].back()] = kc;
				t[i].second[1].pop_back();
			}
		}
		for (int i = n / 2; i < n; ++i) {
			if (one(t[i])) {
				++ones;
				g[t[i].first][t[i].second[1].back()] = kc;
				t[i].second[1].pop_back();
			}
			else {
				++zeros;
				g[t[i].first][t[i].second[0].back()] = kc;
				t[i].second[0].pop_back();
			}
		}	
		ans += min(ones, zeros);
	}
	allocate_tickets(g);
	return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 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
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 32 ms 3836 KB Output is correct
6 Correct 694 ms 70724 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 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 3 ms 460 KB Output is correct
5 Correct 26 ms 2916 KB Output is correct
6 Correct 629 ms 64396 KB Output is correct
7 Correct 664 ms 64616 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 276 KB Output is correct
12 Correct 7 ms 924 KB Output is correct
13 Correct 22 ms 2464 KB Output is correct
14 Correct 21 ms 2380 KB Output is correct
15 Correct 670 ms 63964 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 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 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 32 ms 3836 KB Output is correct
12 Correct 694 ms 70724 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 26 ms 2916 KB Output is correct
18 Correct 629 ms 64396 KB Output is correct
19 Correct 664 ms 64616 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 276 KB Output is correct
24 Correct 7 ms 924 KB Output is correct
25 Correct 22 ms 2464 KB Output is correct
26 Correct 21 ms 2380 KB Output is correct
27 Correct 670 ms 63964 KB Output is correct
28 Runtime error 1 ms 332 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -