oj.uz

Submission #251314

# Submission time Handle Problem Language Result Execution time Memory
251314 2020-07-20T17:32:59 Z Haunted_Cpp Building Bridges (CEOI17_building) C++17
100 / 100
 142 ms 65400 KB 
/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
 
typedef long long i64;
typedef pair<i64, i64> pi64;
 
const i64 INF = 1e18;
const int MAX_N = 1e6 + 5;
 
i64 dp[MAX_N], h[MAX_N], c[MAX_N];
 
i64 f(pi64 linha, int x) {
	return linha.first * x + linha.second;
}
 
struct LiChao {
	vector<pi64> seg;
	LiChao (int n) {
		seg.clear();
		seg = vector<pi64> (4 * n, {0, INF});
	}
	void add(pi64 linha, int l, int r, int node) {
		const int mid = l + (r - l) / 2;
		bool left = f(linha, l) < f(seg[node], l);
		bool middle = f(linha, mid) < f(seg[node], mid);
		if (middle) {
			swap(seg[node], linha);
		}
		if (l == r) {
			return;
		} else if (left != middle) {
			add(linha, l, mid, 2 * node + 1);
		} else {
			add(linha, mid + 1, r, 2 * node + 2);
		}
	}
	i64 get(int l, int r, int node, int where) {
		const int mid = l + (r - l) / 2;
		if (l == r) {
			return f(seg[node], where);
		} else if (where < mid) {
			return min(f(seg[node], where), get(l, mid, 2 * node + 1, where));
		}
		return min(f(seg[node], where), get(mid + 1, r, 2 * node + 2, where));
	}
};
 
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> h[i];
	for (int i = 0; i < n; i++) {
		cin >> c[i];
		if (i) c[i] += c[i - 1];
	}
	LiChao hull(MAX_N);
	dp[0] = 0;
	hull.add({-2 * h[0], dp[0] - c[0] + h[0] * h[0]}, 0, MAX_N, 0);
	for (int i = 1; i < n; i++) dp[i] = 1e18;
	for (int i = 1; i < n; i++) {
		dp[i] = hull.get(0, MAX_N, 0, h[i]);
		dp[i] += h[i] * h[i] + (i - 1 >= 0 ? c[i - 1] : 0);
		hull.add({-2 * h[i], dp[i] - c[i] + h[i] * h[i]}, 0, MAX_N, 0);
	} 
	cout << dp[n - 1] << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62968 KB Output is correct
2 Correct 29 ms 62968 KB Output is correct
3 Correct 34 ms 62968 KB Output is correct
4 Correct 29 ms 62976 KB Output is correct
5 Correct 34 ms 62968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 65272 KB Output is correct
2 Correct 85 ms 65400 KB Output is correct
3 Correct 77 ms 65388 KB Output is correct
4 Correct 84 ms 65272 KB Output is correct
5 Correct 84 ms 65348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62968 KB Output is correct
2 Correct 29 ms 62968 KB Output is correct
3 Correct 34 ms 62968 KB Output is correct
4 Correct 29 ms 62976 KB Output is correct
5 Correct 34 ms 62968 KB Output is correct
6 Correct 76 ms 65272 KB Output is correct
7 Correct 85 ms 65400 KB Output is correct
8 Correct 77 ms 65388 KB Output is correct
9 Correct 84 ms 65272 KB Output is correct
10 Correct 84 ms 65348 KB Output is correct
11 Correct 96 ms 65272 KB Output is correct
12 Correct 86 ms 65272 KB Output is correct
13 Correct 111 ms 65272 KB Output is correct
14 Correct 142 ms 65272 KB Output is correct
15 Correct 109 ms 65272 KB Output is correct
16 Correct 77 ms 65272 KB Output is correct
17 Correct 63 ms 65272 KB Output is correct
18 Correct 63 ms 65272 KB Output is correct