oj.uz

Submission #251312

# Submission time Handle Problem Language Result Execution time Memory
251312 2020-07-20T17:29:52 Z Haunted_Cpp Building Bridges (CEOI17_building) C++17
100 / 100
 95 ms 66556 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 {
	const int L;
	vector<pi64> seg;
	LiChao(int n) : L(n + 5) {
		seg.clear();
		seg = vector<pi64>(4 * L, {0, INF});
	}
	void add(pi64 linha, int l, int r, int node) {
		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 (r == l) {
			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 where, int node) {
		int mid = l + (r - l) / 2;
		if (r == l) {
			return f(seg[node], where);
		} else if (where < mid) {
			return min(f(seg[node], where), get(l, mid, where, 2 * node + 1));
		} else {
			return min(f(seg[node], where), get(mid + 1, r, where, 2 * node + 2));
		}
	}
};
 
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, h[i], 0);
		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 29 ms 62968 KB Output is correct
2 Correct 28 ms 62968 KB Output is correct
3 Correct 28 ms 63104 KB Output is correct
4 Correct 29 ms 62976 KB Output is correct
5 Correct 29 ms 62968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 65528 KB Output is correct
2 Correct 82 ms 66380 KB Output is correct
3 Correct 83 ms 66296 KB Output is correct
4 Correct 88 ms 66296 KB Output is correct
5 Correct 73 ms 66296 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62968 KB Output is correct
2 Correct 28 ms 62968 KB Output is correct
3 Correct 28 ms 63104 KB Output is correct
4 Correct 29 ms 62976 KB Output is correct
5 Correct 29 ms 62968 KB Output is correct
6 Correct 82 ms 65528 KB Output is correct
7 Correct 82 ms 66380 KB Output is correct
8 Correct 83 ms 66296 KB Output is correct
9 Correct 88 ms 66296 KB Output is correct
10 Correct 73 ms 66296 KB Output is correct
11 Correct 95 ms 66556 KB Output is correct
12 Correct 84 ms 66296 KB Output is correct
13 Correct 73 ms 66424 KB Output is correct
14 Correct 83 ms 66552 KB Output is correct
15 Correct 67 ms 66168 KB Output is correct
16 Correct 70 ms 66308 KB Output is correct
17 Correct 65 ms 66552 KB Output is correct
18 Correct 67 ms 66424 KB Output is correct