oj.uz

Submission #98988

# Submission time Handle Problem Language Result Execution time Memory
98988 2019-02-27T23:50:01 Z Anai Popeala (CEOI16_popeala) C++14
100 / 100
 492 ms 1152 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 <= color[pos]; ++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]] = min(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); }
  
		cout << dp[1][tests] << '\n'; }
 
 
	return 0; }

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:67: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 3 ms 512 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 17 ms 640 KB Output is correct
2 Correct 14 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 54 ms 768 KB Output is correct
2 Correct 86 ms 768 KB Output is correct
3 Correct 100 ms 856 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 17 ms 640 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Correct 15 ms 640 KB Output is correct
6 Correct 54 ms 768 KB Output is correct
7 Correct 86 ms 768 KB Output is correct
8 Correct 100 ms 856 KB Output is correct
9 Correct 150 ms 864 KB Output is correct
10 Correct 262 ms 928 KB Output is correct
11 Correct 382 ms 1116 KB Output is correct
12 Correct 374 ms 1016 KB Output is correct
13 Correct 492 ms 1144 KB Output is correct
14 Correct 455 ms 1024 KB Output is correct
15 Correct 462 ms 1152 KB Output is correct