Submission #483797

#	Time	Username	Problem	Language	Result	Execution time	Memory
483797		hollwo_pelw	Popeala (CEOI16_popeala)	C++17	100 / 100	222 ms	9064 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74