oj.uz

Submission #1090714

# Submission time Handle Problem Language Result Execution time Memory
1090714 2024-09-18T15:45:48 Z xnqs Building Bridges (CEOI17_building) C++17
100 / 100
 79 ms 66584 KB 
// dp[1] = 0
// dp[i] = min(dp[j] + (h[i]-h[j])^2 + pfx[i-1] - pfx[j])
// dp[i] = min(dp[j] + h[i]^2 - 2*h[i]*h[j] + h[j]^2 + pfx[i-1] - pfx[j])
// dp[i] = pfx[i-1] + h[i]^2 + min(dp[j] - 2*h[i]*h[j] + h[j]^2 - pfx[j])
//
//         --------i--------       ----ij------   ------------j----------
// dp[i] = pfx[i-1] + h[i]^2 + min(-2*h[i]*h[j] + dp[j] + h[j]^2 - pfx[j])

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

struct Line {
	int64_t m, b;
	Line():
		m(0), b(0x3f3f3f3f3f3f3f3f) {}
	Line(int64_t m, int64_t b):
		m(m), b(b) {}

	int64_t operator() (int x) {
		return m*x + b;
	}
};

class LiChaoTree {
private:
	int n;
	std::vector<Line> tree;
public:
	LiChaoTree(int n): n(n) {
		tree.assign(4*n+1,Line());
	}

	void add_line(int node, int l, int r, Line line) {
		if (l+1==r) {
			if (tree[node](l) > line(l)) {
				tree[node] = line;
			}
			return;
		}

		int m = (l+r)>>1;
		if (tree[node].m > line.m) {
			std::swap(tree[node],line);
		}
		if (tree[node](m) > line(m)) {
			std::swap(tree[node],line);
			add_line(node<<1|1,m,r,line);
		}
		else {
			add_line(node<<1,l,m,line);
		}
	}

	int64_t query(int node, int l, int r, int x) {
		if (l+1==r) {
			return tree[node](x);
		}

		int m = (l+r)>>1;
		if (x<m) {
			return std::min(tree[node](x), query(node<<1,l,m,x));
		}
		else {
			return std::min(tree[node](x), query(node<<1|1,m,r,x));
		}
	}
};

int x;
int height[100005];
int cost[100005];
int64_t pfx_cost[100005];
int64_t dp[100005];

int main() {
	std::cin >> x;
	for (int i = 1; i <= x; i++) {
		std::cin >> height[i];
	}
	for (int i = 1; i <= x; i++) {
		std::cin >> cost[i];
		pfx_cost[i] = pfx_cost[i-1] + cost[i];
	}

	LiChaoTree tree(1000005);
	for (int i = 1; i <= x; i++) {
		if (i==1) {
			dp[i] = 0;
		}
		else {
			dp[i] = pfx_cost[i-1] + 1LL*height[i]*height[i] + tree.query(1,0,1000001,height[i]);
		}
		tree.add_line(1,0,1000001,Line(-2LL*height[i],dp[i]+1LL*height[i]*height[i]-pfx_cost[i]));
	}

	std::cout << dp[x] << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 65116 KB Output is correct
2 Correct 21 ms 65112 KB Output is correct
3 Correct 20 ms 65116 KB Output is correct
4 Correct 22 ms 64892 KB Output is correct
5 Correct 21 ms 65140 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 66272 KB Output is correct
2 Correct 70 ms 66304 KB Output is correct
3 Correct 69 ms 66384 KB Output is correct
4 Correct 63 ms 66132 KB Output is correct
5 Correct 63 ms 66192 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 65116 KB Output is correct
2 Correct 21 ms 65112 KB Output is correct
3 Correct 20 ms 65116 KB Output is correct
4 Correct 22 ms 64892 KB Output is correct
5 Correct 21 ms 65140 KB Output is correct
6 Correct 78 ms 66272 KB Output is correct
7 Correct 70 ms 66304 KB Output is correct
8 Correct 69 ms 66384 KB Output is correct
9 Correct 63 ms 66132 KB Output is correct
10 Correct 63 ms 66192 KB Output is correct
11 Correct 79 ms 66584 KB Output is correct
12 Correct 71 ms 66388 KB Output is correct
13 Correct 63 ms 66388 KB Output is correct
14 Correct 73 ms 66388 KB Output is correct
15 Correct 55 ms 66196 KB Output is correct
16 Correct 55 ms 66128 KB Output is correct
17 Correct 63 ms 66384 KB Output is correct
18 Correct 56 ms 66384 KB Output is correct