oj.uz

Submission #504608

# Submission time Handle Problem Language Result Execution time Memory
504608 2022-01-10T06:47:49 Z dutinmeow Building Bridges (CEOI17_building) C++17
100 / 100
 79 ms 9688 KB 
#include <bits/stdc++.h>
using namespace std;

bool _Line_Comp_State; 
struct Line {
	// k is slope, m is intercept, p is intersection point
	mutable long long k, m, p;
	bool operator<(const Line& o) const {
		return _Line_Comp_State ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
	
	bool isect(iterator x, iterator y) {
		if (y == end()) { 
			x->p = LLONG_MAX; 
			return false; 
		}
		if (x->k == y->k) 
			x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		else 
			x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}

	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) 
			z = erase(z);
		if (x != begin() && isect(--x, y)) 
			isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	
	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1; 
		auto l = *lower_bound({0, 0, x}); 
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};

const int MAX = 1e5 + 5;

int N;
long long H[MAX], W[MAX], dp[MAX];

int main() {
	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];
	}

	LineContainer lc;
	for (int i = 1; i <= N; i++) {
		if (i != 1)
			dp[i] = -lc.query(H[i]) + W[i - 1] + H[i] * H[i];
		lc.add(2 * H[i], -(dp[i] - W[i] + H[i] * H[i]));
	}
	//for (int i = 1; i <= N; i++)
	//	cout << dp[i] << " \n"[i == N];
	cout << dp[N] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3812 KB Output is correct
2 Correct 71 ms 3672 KB Output is correct
3 Correct 65 ms 3612 KB Output is correct
4 Correct 67 ms 3484 KB Output is correct
5 Correct 73 ms 4652 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 72 ms 3812 KB Output is correct
7 Correct 71 ms 3672 KB Output is correct
8 Correct 65 ms 3612 KB Output is correct
9 Correct 67 ms 3484 KB Output is correct
10 Correct 73 ms 4652 KB Output is correct
11 Correct 70 ms 3764 KB Output is correct
12 Correct 77 ms 3652 KB Output is correct
13 Correct 70 ms 3684 KB Output is correct
14 Correct 70 ms 3760 KB Output is correct
15 Correct 79 ms 9688 KB Output is correct
16 Correct 62 ms 4780 KB Output is correct
17 Correct 52 ms 3656 KB Output is correct
18 Correct 53 ms 3636 KB Output is correct