oj.uz

답안 #612311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612311 2022-07-29T12:56:17 Z erekle 카니발 티켓 (IOI20_tickets) C++17
41 / 100
 900 ms 59860 KB 
#include "tickets.h"
#include <vector>
#include <algorithm>
#include <iostream>

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 || MAX == 1) {
		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];
				}
			}
		}
	}
	allocate_tickets(answer);
	return prize;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 756 KB Output is correct
6 Correct 18 ms 9604 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 252 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 24 ms 2324 KB Output is correct
6 Correct 676 ms 51324 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Contestant returned 4 while correct return value is 6.
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 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 3 ms 500 KB Output is correct
5 Correct 31 ms 2548 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 10 ms 852 KB Output is correct
8 Correct 835 ms 59860 KB Output is correct
9 Correct 900 ms 58048 KB Output is correct
10 Correct 832 ms 58020 KB Output is correct
11 Correct 835 ms 59824 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 2 ms 372 KB There is no ticket of color 0 on day 0
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 2 ms 372 KB There is no ticket of color 0 on day 0
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 756 KB Output is correct
6 Correct 18 ms 9604 KB Output is correct
7 Correct 1 ms 252 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 24 ms 2324 KB Output is correct
12 Correct 676 ms 51324 KB Output is correct
13 Incorrect 0 ms 212 KB Contestant returned 4 while correct return value is 6.
14 Halted 0 ms 0 KB -