oj.uz

Submission #612386

# Submission time Handle Problem Language Result Execution time Memory
612386 2022-07-29T13:54:41 Z erekle Carnival Tickets (IOI20_tickets) C++17
41 / 100
 733 ms 59868 KB 
#include "tickets.h"
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const long long INF = 1e18;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

	vector<vector<int>> answer(n, vector<int>(m, -1));
	long long prize = 0;

	int MAX = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			MAX = max(MAX, x[i][j]);
		}
	}

	if (k == 1) {
		vector<vector<long long>> dp(1+n, vector<long long>(1+n/2, -INF));
		dp[0][0] = 0;
		// dp on prefix and number of positives
		vector<vector<bool>> chosePositive(1+n, vector<bool>(1+n/2));
		// chosePositive allows backtracking
		for (int i = 0; i < n; ++i) {
			for (int pos = 0; 2*pos <= n; ++pos) {
				if (dp[i][pos] == -INF) continue;

				// do not choose positive
				long long v = dp[i][pos] - x[i].front();
				if (v > dp[i+1][pos]) {
					dp[i+1][pos] = v;
					chosePositive[i+1][pos] = false;
				}

				// choose positive (if possible)
				if (2*pos == n) continue; // no more positives
				v = dp[i][pos] + x[i].back();
				if (v > dp[i+1][pos+1]) {
					dp[i+1][pos+1] = v;
					chosePositive[i+1][pos+1] = true;
				}
			}
		}

		prize = dp[n][n>>1];
		// Now reconstruct answer
		for (int i = n, pos = n>>1; i >= 1; --i) {
			if (!chosePositive[i][pos]) answer[i-1][0] = 0;
			else answer[i-1][m-1] = 0, pos--;
		}
	} else if (m == k) {
		vector<int> cnt[2], remain[2];
		cnt[0].resize(n), cnt[1].resize(n);
		remain[0].resize(n), remain[1].resize(n);

		vector<pair<int, int>> v;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
		}
		sort(v.begin(), v.end());
		for (int i = 0; (i<<1) < n*m; ++i) {
			++cnt[0][v[i].second];
		}
		for (int i = 0; i < n; ++i) {
			cnt[1][i] = m-cnt[0][i];
			remain[0][i] = cnt[0][i];
			remain[1][i] = cnt[1][i];
		}

		for (int i = 0; i < k; ++i) {
			int used0 = 0;
			for (int y = 0; y < n; ++y) {
				if (!remain[1][y]) { // zero
					prize -= x[y][cnt[0][y]-remain[0][y]];
					answer[y][cnt[0][y]-remain[0][y]] = i;
					--remain[0][y];
					++used0;
				} else if (!remain[0][y]) { // one
					prize += x[y][cnt[0][y]+remain[1][y]-1];
					answer[y][cnt[0][y]+remain[1][y]-1] = i;
					--remain[1][y];
				}
			}
			for (int y = 0; y < n; ++y) { // both
				if (!remain[0][y] || !remain[1][y]) continue;
				if (2*used0 < n) {
					prize -= x[y][cnt[0][y]-remain[0][y]];
					answer[y][cnt[0][y]-remain[0][y]] = i;
					--remain[0][y];
					++used0;
				} else {
					prize += x[y][cnt[0][y]+remain[1][y]-1];
					answer[y][cnt[0][y]+remain[1][y]-1] = i;
					--remain[1][y];
				}
			}
		}
	} else if (MAX == 1) {
		int z = 0, o = 0;
		vector<int> got0(n), got1(n);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (x[i][j] == 0) ++z, ++got0[i];
				else ++o, ++got1[i];
			}
		}
		// have to remove (m-k)*n
		int zTarget = 0, rem = (m-k)*n;
		zTarget = (rem+(z-o))/2;
		int mnRemove = 0, mxRemove = 0; // zeros removed
		vector<int> mn(1+n), mx(1+n);
		for (int i = 0; i < n; ++i) {
			mnRemove += max(m-k-got1[i], 0);
			mxRemove += min(m-k, got0[i]);
			mn[i+1] = mnRemove;
			mx[i+1] = mxRemove;
		}

		// Recalculate realistic target
		if (zTarget < mnRemove) zTarget = mnRemove;
		if (zTarget > mxRemove) zTarget = mxRemove;

		// Remove so that target is achieved
		vector<int> removed0(n), removed1(n);
		for (int i = n; i >= 1; --i) {
			int least = max(m-k-got1[i-1], 0);
			int most = min(m-k, got0[i-1]);
			int largestAfter = mx[i-1];
			removed0[i-1] = max(zTarget-largestAfter, least);
			assert(least <= removed0[i-1] && removed0[i-1] <= most);
			removed1[i-1] = m-k-removed0[i-1];
			zTarget -= removed0[i-1];
		}

		// This is the same as the solution to m=k except one detail below
		vector<int> cnt[2], remain[2];
		cnt[0].resize(n), cnt[1].resize(n);
		remain[0].resize(n), remain[1].resize(n);

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (x[i][j] == 0) ++cnt[0][i];
			}
		}
		// vector<pair<int, int>> v;
		// for (int i = 0; i < n; ++i) {
		// 	for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
		// }
		// sort(v.begin(), v.end());
		// for (int i = 0; (i<<1) < n*m; ++i) {
		// 	++cnt[0][v[i].second];
		// }
		for (int i = 0; i < n; ++i) {
			cnt[1][i] = m-cnt[0][i];
			remain[0][i] = cnt[0][i];
			remain[1][i] = cnt[1][i];
			// Here we are subtracting removed from remain
			remain[0][i] -= removed0[i];
			remain[1][i] -= removed1[i];
			assert(remain[0][i] >= 0 && remain[0][i] <= cnt[0][i]);
			assert(remain[1][i] >= 0 && remain[1][i] <= cnt[1][i]);
		}

		for (int i = 0; i < k; ++i) {
			int used0 = 0;
			for (int y = 0; y < n; ++y) {
				if (!remain[1][y]) { // zero
					assert(remain[0][y]);
					prize -= x[y][cnt[0][y]-remain[0][y]];
					answer[y][cnt[0][y]-remain[0][y]] = i;
					--remain[0][y];
					++used0;
				} else if (!remain[0][y]) { // one
					assert(remain[1][y]);
					prize += x[y][cnt[0][y]+remain[1][y]-1];
					answer[y][cnt[0][y]+remain[1][y]-1] = i;
					--remain[1][y];
				}
			}
			for (int y = 0; y < n; ++y) { // both
				if (!remain[0][y] || !remain[1][y]) continue;
				if (2*used0 < n) {
					prize -= x[y][cnt[0][y]-remain[0][y]];
					answer[y][cnt[0][y]-remain[0][y]] = i;
					--remain[0][y];
					++used0;
				} else {
					prize += x[y][cnt[0][y]+remain[1][y]-1];
					answer[y][cnt[0][y]+remain[1][y]-1] = i;
					--remain[1][y];
				}
			}
		}
	}
	allocate_tickets(answer);
	return prize;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 15 ms 9556 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 21 ms 2316 KB Output is correct
6 Correct 512 ms 51304 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 18 ms 2336 KB Output is correct
6 Correct 442 ms 52292 KB Output is correct
7 Correct 448 ms 52668 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Incorrect 14 ms 2024 KB There is no ticket of color 0 on day 0
14 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 32 ms 2448 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 8 ms 844 KB Output is correct
8 Correct 720 ms 59868 KB Output is correct
9 Correct 688 ms 58060 KB Output is correct
10 Correct 709 ms 58008 KB Output is correct
11 Correct 733 ms 59832 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB There is no ticket of color 0 on day 0
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB There is no ticket of color 0 on day 0
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 15 ms 9556 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 21 ms 2316 KB Output is correct
12 Correct 512 ms 51304 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 2 ms 416 KB Output is correct
17 Correct 18 ms 2336 KB Output is correct
18 Correct 442 ms 52292 KB Output is correct
19 Correct 448 ms 52668 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Incorrect 14 ms 2024 KB There is no ticket of color 0 on day 0
26 Halted 0 ms 0 KB -