oj.uz

Submission #125885

# Submission time Handle Problem Language Result Execution time Memory
125885 2019-07-06T13:46:58 Z tutis Popeala (CEOI16_popeala) C++17
26 / 100
 1632 ms 262144 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 ST
{
	int l, r;
	vector<line>K;
	ST *left;
	ST *right;
	ll ans[51];
	ST(int l, int r, const vector<line>&xx): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2, xx);
			right = new ST((l + r) / 2 + 1, r, xx);
		}
		for (ll x = 0; x <= 50; x++)
		{
			ans[x] = 1e15;
			for (int i = l; i <= r; i++)
			{
				ans[x] = min(ans[x], xx[i].k * x + xx[i].b);
			}
		}
	}
	ll mini(int x, int y, ll xx)
	{
		if (x <= l && r <= y)
			return ans[xx];
		if (r < x || y < l)
			return 1e15;
		return min(left->mini(x, y, xx), right->mini(x, y, xx));
	}
};
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);
	for (int c = 1; c <= S; c++)
	{
		vector<line>aaa;
		for (int a = 0; a <= T; a++)
		{
			aaa.push_back(line());
			aaa.back().b = dp[c - 1][a];
			aaa.back().k = -p[a];
		}
		ST medis(0, aaa.size() - 1, aaa);
		for (int b = 1; b <= T; b++)
		{
			int l = 1;
			for (int x = 0; x <= N; x++)
			{
				int r = kada[b][x];
				ll mini = medis.mini(l - 1, r - 1, x);
				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";
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:48:14: warning: 'medis.ST::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return min(left->mini(x, y, xx), right->mini(x, y, xx));
              ^~~~
popeala.cpp:102:6: note: 'medis.ST::right' was declared here
   ST medis(0, aaa.size() - 1, aaa);
      ^~~~~
popeala.cpp:48:14: warning: 'medis.ST::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return min(left->mini(x, y, xx), right->mini(x, y, xx));
              ^~~~
popeala.cpp:102:6: note: 'medis.ST::left' was declared here
   ST medis(0, aaa.size() - 1, aaa);
      ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 23420 KB Output is correct
2 Correct 101 ms 23416 KB Output is correct
3 Correct 103 ms 23416 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 101792 KB Output is correct
2 Correct 796 ms 138712 KB Output is correct
3 Correct 1102 ms 184824 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 103 ms 23420 KB Output is correct
4 Correct 101 ms 23416 KB Output is correct
5 Correct 103 ms 23416 KB Output is correct
6 Correct 526 ms 101792 KB Output is correct
7 Correct 796 ms 138712 KB Output is correct
8 Correct 1102 ms 184824 KB Output is correct
9 Runtime error 1632 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -