Submission #125913

#	Time	Username	Problem	Language	Result	Execution time	Memory
125913		tutis	Popeala (CEOI16_popeala)	C++17	26 / 100	2073 ms	131320 KiB

popeala

/*input
2 3 3
4 3 5
101
110
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = 1000000007;
struct line
{
	ll k;
	ll b;
	// kx + b
};
struct mini
{
	vector<ll>P[15];
	mini()
	{
		for (int i = 0; i < 15; i++)
			P[i] = vector<ll>(20000);
	}
	ll get(ll x, ll y)
	{
		if (x > y)
			return 1e15;
		if (x == y)
			return P[0][x];
		int sz = y - x + 1;
		int t = log2(sz);
		return min(P[t][x], P[t][y - (1 << t) + 1]);
	}
	void fix()
	{
		for (int t = 1; t < 15; t++)
		{
			int s = (1 << (t - 1));
			for (int i = 0; i + s < 20000; i++)
			{
				P[t][i] = min(P[t - 1][i], P[t - 1][i + s]);
			}
		}
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	ll N, T, S;
	cin >> N >> T >> S;
	ll p[T + 1];
	p[0] = 0;
	for (ll i = 1; i <= T; i++)
	{
		cin >> p[i];
		p[i] += p[i - 1];
	}
	string res[N];
	for (ll i = 0; i < N; i++)
		cin >> res[i];
	ll dp[S + 1][T + 1];
	for (ll a = 0; a <= S; a++)
	{
		for (ll b = 0; b <= T; b++)
		{
			dp[a][b] = 1e11;
		}
	}
	dp[0][0] = 0;
	int kada[T + 1][N + 1];
	for (int i = 0; i <= N; i++)
		kada[0][i] = 0;
	for (ll b = 1; b <= T; b++)
	{
		for (ll i = 0; i < N; i++)
		{
			if (res[i][b - 1] == '0')
			{
				kada[b][i] = b;
			}
			else
				kada[b][i] = kada[b - 1][i];
		}
		kada[b][N] = b;
	}
	for (ll b = 1; b <= T; b++)
		sort(kada[b], kada[b] + N + 1);
	mini xxx[N + 1];
	for (int c = 1; c <= S; c++)
	{
		for (int x = 0; x <= N; x++)
		{
			for (int a = 0; a < T; a++)
			{
				xxx[x].P[0][a] = dp[c - 1][a] - x * p[a];
			}
			xxx[x].fix();
		}
		for (int b = 1; b <= T; b++)
		{
			int l = 1;
			for (int x = 0; x <= N; x++)
			{
				int r = kada[b][x];
				ll mini = xxx[x].get(l - 1, r - 1);
				dp[c][b] = min(dp[c][b], mini + x * p[b]);
				l = r + 1;
			}
		}
	}
	for (ll c = 1; c <= S; c++)
	{
		cout << dp[c][T] << "\n";
	}
}

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