oj.uz

Submission #528082

# Submission time Handle Problem Language Result Execution time Memory
528082 2022-02-19T07:15:10 Z sidon Building Bridges (CEOI17_building) C++17
100 / 100
 60 ms 36648 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int SZ = 1<<20, INF = 1e16;

struct Line {
	int m = 0, c = INF;
	Line() {}
	int operator()(int x) { return m * x + c; }
};

Line s[SZ<<1], u;

void add(int x, int l, int r) {
	int m = (l + r) / 2;
	if(s[x](m) > u(m)) swap(u, s[x]);
	if(r - l > 1)
		u.m >= s[x].m ? add(2*x, l, m) : add(2*x+1, m, r);
}

const int Z = 1e5+1;

int N, h[Z], w[Z], dp[Z];

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

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

	for(int i = 1; i <= N; ++i) {
		cin >> w[i];
		w[i] += w[i-1];
		dp[i] = INF;
	}

	for(int i = 1; i <= N; ++i) {

		for(int j = h[i] + SZ; j; j/=2)
			dp[i] = min(dp[i], s[j](h[i]));

		dp[i] += h[i] * h[i] + w[i-1];
		if(i < 2) dp[i] = 0;

		u.m = - 2 * h[i];
		u.c = dp[i] + h[i] * h[i] - w[i];

		add(1, 0, SZ);
	}

	cout << dp[N];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33100 KB Output is correct
2 Correct 20 ms 33128 KB Output is correct
3 Correct 18 ms 33116 KB Output is correct
4 Correct 15 ms 33188 KB Output is correct
5 Correct 16 ms 33256 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 36484 KB Output is correct
2 Correct 50 ms 36492 KB Output is correct
3 Correct 48 ms 36452 KB Output is correct
4 Correct 51 ms 36408 KB Output is correct
5 Correct 46 ms 36412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33100 KB Output is correct
2 Correct 20 ms 33128 KB Output is correct
3 Correct 18 ms 33116 KB Output is correct
4 Correct 15 ms 33188 KB Output is correct
5 Correct 16 ms 33256 KB Output is correct
6 Correct 47 ms 36484 KB Output is correct
7 Correct 50 ms 36492 KB Output is correct
8 Correct 48 ms 36452 KB Output is correct
9 Correct 51 ms 36408 KB Output is correct
10 Correct 46 ms 36412 KB Output is correct
11 Correct 60 ms 36560 KB Output is correct
12 Correct 54 ms 36488 KB Output is correct
13 Correct 47 ms 36544 KB Output is correct
14 Correct 60 ms 36648 KB Output is correct
15 Correct 54 ms 36352 KB Output is correct
16 Correct 43 ms 36384 KB Output is correct
17 Correct 41 ms 36480 KB Output is correct
18 Correct 39 ms 36548 KB Output is correct