Submission #98982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98982	2019-02-27T21:40:15 Z	Anai	Popeala (CEOI16_popeala)	C++14	26 / 100	572 ms	2168 KB

popeala

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-