oj.uz

Submission #125917

# Submission time Handle Problem Language Result Execution time Memory
125917 2019-07-06T14:13:00 Z tutis Popeala (CEOI16_popeala) C++17
100 / 100
 1879 ms 137592 KB 
/*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;
		int sz = y - x + 1;
		int t = 31 - __builtin_clz(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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7544 KB Output is correct
2 Correct 295 ms 86904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 123256 KB Output is correct
2 Correct 1130 ms 118556 KB Output is correct
3 Correct 1162 ms 123384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1165 ms 119588 KB Output is correct
2 Correct 1241 ms 125084 KB Output is correct
3 Correct 1275 ms 125788 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7544 KB Output is correct
2 Correct 295 ms 86904 KB Output is correct
3 Correct 1169 ms 123256 KB Output is correct
4 Correct 1130 ms 118556 KB Output is correct
5 Correct 1162 ms 123384 KB Output is correct
6 Correct 1165 ms 119588 KB Output is correct
7 Correct 1241 ms 125084 KB Output is correct
8 Correct 1275 ms 125788 KB Output is correct
9 Correct 1389 ms 127420 KB Output is correct
10 Correct 1490 ms 128632 KB Output is correct
11 Correct 1766 ms 131448 KB Output is correct
12 Correct 1774 ms 137564 KB Output is correct
13 Correct 1863 ms 137592 KB Output is correct
14 Correct 1879 ms 137508 KB Output is correct
15 Correct 1859 ms 137512 KB Output is correct