Submission #610400

#	Time	Username	Problem	Language	Result	Execution time	Memory
610400		Drew_	Popeala (CEOI16_popeala)	C++17	100 / 100	1691 ms	15256 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define size(x) (int)x.size()

const int MAX = 2e4 + 69;
const int inf = 2e9 + 69;

int N, S, T;
int ar[MAX], pfx[MAX];
int prv[69][MAX]; // prv[i][j]: closest '0' to the left from task `j` for contestant `i`
int dp[69][MAX];

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> T >> S;
	for (int i = 1; i <= T; ++i)
		cin >> ar[i], pfx[i] = ar[i] + pfx[i-1];

	for (int i = 1; i <= N; ++i)
	{
		char s[MAX]; cin >> (s+1);
		for (int j = 1; j <= T; ++j)
		{
			if (s[j] == '0') prv[i][j] = j;
			else prv[i][j] = prv[i][j-1];
		}
	}

	for (int i = 0; i < 69; ++i)
		fill(dp[i], dp[i] + MAX, inf);
	dp[0][0] = 0;

	int val[MAX][69] = {};
	for (int g = 1; g <= S; ++g)
	{
		for (int i = 0; i <= T; ++i)
			for (int j = 0; j <= N; ++j)
				val[i][j] = inf;

		for (int i = 1; i <= T; ++i)
		{
			vector<int> v = { 1 };
			for (int j = 1; j <= N; ++j) if (prv[j][i] < i)
				v.pb(prv[j][i] + 1);
			sort(v.begin(), v.end());

			for (int j = 0; j <= N; ++j)
				val[i][j] = min(val[i-1][j], dp[g-1][i-1] - j * pfx[i-1]);
			for (int j = 0; j < size(v); ++j)
				dp[g][i] = min(dp[g][i], j * pfx[i] + val[(j+1 < size(v) ? v[j+1] - 1 : i)][j]);
		}
	}
	
	for (int g = 1; g <= S; ++g)
		cout << dp[g][T] << '\n';

	return 0;
}

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