Submission #1241797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241797		kaiboy	Popeala (CEOI16_popeala)	C++20	100 / 100	159 ms	9560 KiB

popeala

#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 20000;
const int   M = 50;
const int INF = 0x7fffffff;

int aa[N + 1], dp[N + 1], dq[M + 1][N + 1];
char cc[M][N + 1];
int pp[N + 1][M + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int m, n, k; cin >> m >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> aa[i], aa[i] += aa[i - 1];
	for (int h = 0; h < m; h++)
		cin >> cc[h];
	for (int h = 0; h < m; h++)
		for (int p = 0, i = 1; i <= n; i++) {
			if (cc[h][i - 1] == '0')
				p = i;
			pp[i][h] = p;
		}
	for (int i = 1; i <= n; i++) {
		pp[i][m] = i;
		sort(pp[i], pp[i] + m + 1);
	}
	for (int i = 0; i <= n; i++)
		dp[i] = INF;
	dp[0] = 0;
	while (k--) {
		for (int c = 0; c <= m; c++)
			for (int x = INF, i = 0; i <= n; i++) {
				if (dp[i] != INF)
					x = min(x, dp[i] - aa[i] * c);
				dq[c][i] = x;
			}
		for (int i = 0; i <= n; i++) {
			int x = INF;
			for (int c = 0; c <= m; c++) {
				int p = pp[i][c];
				if (p && dq[c][p - 1] != INF)
					x = min(x, dq[c][p - 1] + aa[i] * c);
			}
			dp[i] = x;
		}
		cout << dp[n] << '\n';
	}
	return 0;
}

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