oj.uz

Submission #483797

# Submission time Handle Problem Language Result Execution time Memory
483797 2021-11-01T04:59:00 Z hollwo_pelw Popeala (CEOI16_popeala) C++17
100 / 100
 222 ms 9064 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 55, T = 20005, S = 55;

int n, s, t, p[T], fail[T][N], dp[S][T], pre[N];

inline void chkmin(int &a, int b) { a = a < b ? a : b; }

signed main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

	cin >> n >> t >> s;
	for (int i = 1; i <= t; i++)
		cin >> p[i], p[i] += p[i - 1];
	for (int i = 0; i < n; i++) {
		string r; cin >> r;
		for (int j = 0; j < t; j++)
			fail[j + 1][i] = r[j] == '0' ? j + 1 : fail[j][i];
	}
	for (int i = 1; i <= t; i++)
		sort(fail[i], fail[i] + n), fail[i][n] = i;
// 	for (int i = 0; i <= n; i++)
// 	    for (int j = 1; j <= t; j++)
// 	        cout << fail[j][i] << " \n"[j == t];
	memset(dp, 0x3f, sizeof dp);
	dp[0][0] = 0;
	// dp[i][j] = min dp[i - 1][k] + (p[j] - p[k]) * (\sum fail[j] >= k)
	// dp[i][j] = min x (min (dp[i - 1][k] - p[k] * x) + p[j] * x (k >= fail[j][x]))
	for (int i = 1; i <= s; i++) {
		memset(pre, 0x3f, sizeof pre);
		for (int j = 1; j <= t; j++) {
			for (int x = 0; x <= n; x++) {
				for (int k = fail[j - 1][x]; k < fail[j][x]; k++)
					chkmin(pre[x], dp[i - 1][k] - p[k] * x);
				chkmin(dp[i][j], pre[x] + p[j] * x);
			}
		}

		cout << dp[i][t] << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4556 KB Output is correct
2 Correct 2 ms 4556 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4684 KB Output is correct
2 Correct 7 ms 4744 KB Output is correct
3 Correct 8 ms 4744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5068 KB Output is correct
2 Correct 47 ms 5300 KB Output is correct
3 Correct 50 ms 5516 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4556 KB Output is correct
2 Correct 2 ms 4556 KB Output is correct
3 Correct 8 ms 4684 KB Output is correct
4 Correct 7 ms 4744 KB Output is correct
5 Correct 8 ms 4744 KB Output is correct
6 Correct 34 ms 5068 KB Output is correct
7 Correct 47 ms 5300 KB Output is correct
8 Correct 50 ms 5516 KB Output is correct
9 Correct 58 ms 5964 KB Output is correct
10 Correct 106 ms 6448 KB Output is correct
11 Correct 160 ms 9004 KB Output is correct
12 Correct 170 ms 9064 KB Output is correct
13 Correct 222 ms 9060 KB Output is correct
14 Correct 216 ms 9056 KB Output is correct
15 Correct 222 ms 9000 KB Output is correct