Submission #98988

#	Time	Username	Problem	Language	Result	Execution time	Memory
98988		Anai	Popeala (CEOI16_popeala)	C++14	100 / 100	492 ms	1152 KiB

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]);
		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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74