oj.uz

답안 #98983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98983 2019-02-27T21:41:08 Z Anai 조교 (CEOI16_popeala) C++14
26 / 100
 513 ms 1416 KB 
#include <bits/stdc++.h>
#define int i64
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;


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; }

Compilation message

popeala.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 900 KB Output is correct
2 Correct 75 ms 944 KB Output is correct
3 Correct 88 ms 1024 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 14 ms 768 KB Output is correct
4 Correct 14 ms 768 KB Output is correct
5 Correct 15 ms 768 KB Output is correct
6 Correct 54 ms 900 KB Output is correct
7 Correct 75 ms 944 KB Output is correct
8 Correct 88 ms 1024 KB Output is correct
9 Correct 133 ms 1024 KB Output is correct
10 Correct 192 ms 1024 KB Output is correct
11 Correct 333 ms 1416 KB Output is correct
12 Correct 347 ms 1360 KB Output is correct
13 Correct 433 ms 1400 KB Output is correct
14 Incorrect 513 ms 1280 KB Output isn't correct
15 Halted 0 ms 0 KB -