oj.uz

답안 #98982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98982 2019-02-27T21:40:15 Z Anai 조교 (CEOI16_popeala) C++14
26 / 100
 572 ms 2168 KB 
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int T = 2e4 + 5, N = 55;

i64 best[N];
bitset<T> mx[N];
int dp[2][T], score[T], color[T], sum[T], ptr[N];


int players, tests, bound;


int main() {
#ifdef HOME
	freopen("popeala.in", "r", stdin);
	freopen("popeala.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> players >> tests >> bound;
	for (int i = 1; i <= tests; ++i) {
		cin >> score[i];
		sum[i] = sum[i - 1] + score[i]; }

	for (int i = 1; i <= players; ++i) {
		string line;
		cin >> line;
		for (int j = 0; j < tests; ++j)
			mx[i][j + 1] = line[j] - '0'; }

	for (int i = 1; i <= players; ++i)
		for (int j = 1; j <= tests && mx[i][j]; ++j)
			dp[1][j]+= sum[j];

	cout << dp[1][tests] << '\n';
	for (int it = 2; it <= bound; ++it) {
		swap(dp[0], dp[1]);
		best[0] = 2e9;
		for (int i = 1; i <= players; ++i) {
			best[i] = 2e9;
			ptr[i] = mx[i][it] ? it : -1; }

		for (int pos = it; pos <= tests; ++pos) {
			color[pos] = 0;
			for (int boy = 1; boy <= players; ++boy) if (mx[boy][pos]) {
				color[pos]+= 1;
				if (ptr[boy] == -1)
					ptr[boy] = pos; }

			for (int boy = 1; boy <= players; ++boy) if (!mx[boy][pos] && ptr[boy] != -1) {
				for (int i = color[ptr[boy]] + 1; i <= players; ++i)
					best[i] = 2e9;

				for (int i = ptr[boy]; i < pos; ++i) {
					color[i]-= 1;
					if (color[i - 1] != color[i])
						best[color[i]] = 2e9;
					best[color[i]] = min(best[color[i]], dp[0][i - 1] - 1LL * sum[i - 1] * color[i]); }

				ptr[boy] = -1; }


			best[color[pos]] = dp[0][pos - 1] - sum[pos - 1] * color[pos];


			dp[1][pos] = 2e9;
			for (int cnt = 0; cnt <= players; ++cnt) // deque lookup
				dp[1][pos] = min(i64(dp[1][pos]), best[cnt] + sum[pos] * cnt); }

		cout << dp[1][tests] << '\n'; }


	return 0; }

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 640 KB Output is correct
2 Correct 13 ms 640 KB Output is correct
3 Correct 15 ms 640 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 840 KB Output is correct
2 Correct 87 ms 888 KB Output is correct
3 Correct 101 ms 896 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 16 ms 640 KB Output is correct
4 Correct 13 ms 640 KB Output is correct
5 Correct 15 ms 640 KB Output is correct
6 Correct 60 ms 840 KB Output is correct
7 Correct 87 ms 888 KB Output is correct
8 Correct 101 ms 896 KB Output is correct
9 Correct 146 ms 1136 KB Output is correct
10 Correct 229 ms 1280 KB Output is correct
11 Correct 383 ms 2040 KB Output is correct
12 Correct 496 ms 2052 KB Output is correct
13 Correct 489 ms 2168 KB Output is correct
14 Incorrect 572 ms 2040 KB Output isn't correct
15 Halted 0 ms 0 KB -