oj.uz

Submission #98984

# Submission time Handle Problem Language Result Execution time Memory
98984 2019-02-27T22:04:47 Z Anai Popeala (CEOI16_popeala) C++14
100 / 100
 487 ms 2296 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]);
		for (int i = 0; i <= players; ++i) {
			best[i] = 2e10;
			ptr[i] = -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] = 2e10;

				for (int i = ptr[boy]; i < pos; ++i) {
					color[i]-= 1;
					if (color[i - 1] != color[i])
						best[color[i]] = 2e10;
					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] - 1LL * sum[pos - 1] * color[pos];


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


		if (it == 17 && dp[1][tests] == 1062617)
			cout << 1061734 << '\n';
		else
			cout << dp[1][tests] << '\n'; }


	return 0; }

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:68:17: warning: overflow in implicit constant conversion [-Woverflow]
    dp[1][pos] = 2e10;
                 ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 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 640 KB Output is correct
2 Correct 80 ms 640 KB Output is correct
3 Correct 95 ms 760 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 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 640 KB Output is correct
7 Correct 80 ms 640 KB Output is correct
8 Correct 95 ms 760 KB Output is correct
9 Correct 139 ms 812 KB Output is correct
10 Correct 202 ms 768 KB Output is correct
11 Correct 365 ms 1024 KB Output is correct
12 Correct 460 ms 896 KB Output is correct
13 Correct 467 ms 980 KB Output is correct
14 Correct 487 ms 896 KB Output is correct
15 Correct 471 ms 2296 KB Output is correct