oj.uz

Submission #531418

# Submission time Handle Problem Language Result Execution time Memory
531418 2022-02-28T16:22:33 Z blue Building Bridges (CEOI17_building) C++17
100 / 100
 58 ms 36676 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())

const int mxh = (1<<20);
const ll INF = 1'000'000'000'000'000'000LL;

struct segtree
{
	vll a = vll(mxh<<1, 0);
	vll b = vll(mxh<<1, INF);

	void addline(ll A, ll B, int i = 1, ll l = 0, ll r = 1'000'000)
	{
		if(A * l + B <= a[i] * l + b[i]  &&  A * r + B <= a[i] * r + b[i])
		{
			a[i] = A;
			b[i] = B;
			return;
		}

		if(A * l + B >= a[i] * l + b[i]  && A * r + B >= a[i] * r + b[i])
		{
			return;
		}

		ll m = (l+r)/2;


		if(A * l + B <= a[i] * l + b[i])
		{
			if(A * m + B <= a[i] * m + b[i])
			{
				addline(a[i], b[i], 2*i+1, m+1, r);
				a[i] = A;
				b[i] = B;
			}
			else
			{
				addline(A, B, 2*i, l, m);
			}
		}
		else
		{
			if(A * (m+1) + B <= a[i] * (m+1) + b[i])
			{
				addline(a[i], b[i], 2*i, l, m);
				a[i] = A;
				b[i] = B;
			}
			else
			{
				addline(A, B, 2*i+1, m+1, r);
			}
		}
	}

	ll query(ll x, int i = 1, ll l = 0, ll r = 1'000'000)
	{
		if(l == r) return a[i] * x + b[i];
		else if(x <= (l+r)/2) return min(a[i] * x + b[i], query(x, 2*i, l, (l+r)/2));
		else return min(a[i] * x + b[i], query(x, 2*i+1, (l+r)/2+1, r));
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	ll h[1+n];
	for(int i = 1; i <= n; i++) cin >> h[i];

	ll wsum[1+n];
	wsum[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> wsum[i];
		wsum[i] += wsum[i-1];
	}

	ll dp[1+n];
	dp[1] = 0;

	segtree lct;

	lct.addline(-2 * h[1], dp[1] + h[1]*h[1] - wsum[1]);


	for(int i = 2; i <= n; i++)
	{
		dp[i] = h[i]*h[i] + wsum[i-1] + lct.query(h[i]);
		lct.addline(-2 * h[i], dp[i] + h[i]*h[i] - wsum[i]);
	}

	cout << dp[n] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33068 KB Output is correct
2 Correct 14 ms 33092 KB Output is correct
3 Correct 14 ms 33076 KB Output is correct
4 Correct 14 ms 33120 KB Output is correct
5 Correct 15 ms 33080 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 36412 KB Output is correct
2 Correct 52 ms 36516 KB Output is correct
3 Correct 50 ms 36420 KB Output is correct
4 Correct 46 ms 36400 KB Output is correct
5 Correct 47 ms 36316 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33068 KB Output is correct
2 Correct 14 ms 33092 KB Output is correct
3 Correct 14 ms 33076 KB Output is correct
4 Correct 14 ms 33120 KB Output is correct
5 Correct 15 ms 33080 KB Output is correct
6 Correct 52 ms 36412 KB Output is correct
7 Correct 52 ms 36516 KB Output is correct
8 Correct 50 ms 36420 KB Output is correct
9 Correct 46 ms 36400 KB Output is correct
10 Correct 47 ms 36316 KB Output is correct
11 Correct 58 ms 36676 KB Output is correct
12 Correct 54 ms 36572 KB Output is correct
13 Correct 43 ms 36520 KB Output is correct
14 Correct 54 ms 36576 KB Output is correct
15 Correct 48 ms 36272 KB Output is correct
16 Correct 58 ms 36396 KB Output is correct
17 Correct 33 ms 36460 KB Output is correct
18 Correct 36 ms 36524 KB Output is correct