oj.uz

Submission #727639

# Submission time Handle Problem Language Result Execution time Memory
727639 2023-04-21T04:28:52 Z NeroZein Building Bridges (CEOI17_building) C++17
60 / 100
 3000 ms 7588 KB 
#include <bits/stdc++.h>
#define int long long 
using namespace std;
 
const int N = 100005;
const int M = 1000006;
 
struct Line {
	int m, b;
	Line () {}
	Line (int m_, int b_ ) : m(m_), b(b_) {}
	int val (int x) {
		return m * x + b; 
	}
};
 
int rt, idd; 
int L[N << 2], R[N << 2]; 
Line seg[N << 2];
 
inline void upd (int& nd, int l, int r, Line line) {
	if (nd == 0) {
		nd = ++idd;
		assert(nd < N * 4); 
		seg[nd] = line;
		return; 
	}
	int mid = (l + r) >> 1; 
	bool f1 = line.val(l) < seg[nd].val(l);
	bool f2 = line.val(mid) < seg[nd].val(mid); 
	if (f2) {
		swap(seg[nd], line);
	}
	if (f1 != f2) {
		return upd(L[nd], l, mid, line); 
	} else {
		return upd(R[nd], mid + 1, r, line); 
	}
}
 
inline int qry (int nd, int l, int r, int x) {
	int me = seg[nd].val(x);
	if (!nd) {
		return 1e18; 
	}
	if (l == r) {
		return me; 
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		return min(me, qry(L[nd], l, mid, x));
	} else {
		return min(me, qry(R[nd], mid + 1, r, x)); 
	}
}
 
int n;
int h[N], w[N];
int pref[N]; 
int dp[N]; 
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		pref[i] = pref[i - 1] + w[i];
	}
	upd(rt, 0, M, Line(-2 * h[1], h[1] * h[1] - pref[1]));
	for (int i = 2; i <= n; ++i) {
		dp[i] = h[i] * h[i] + pref[i - 1] + qry(rt, 0, M, h[i]);
		upd(rt, 0, M, Line(-2 * h[i], h[i] * h[i] - pref[i] + dp[i])); 
	}
	cout << dp[n] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7432 KB Output is correct
2 Correct 95 ms 7380 KB Output is correct
3 Correct 94 ms 7368 KB Output is correct
4 Correct 150 ms 7004 KB Output is correct
5 Correct 30 ms 7416 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 92 ms 7432 KB Output is correct
7 Correct 95 ms 7380 KB Output is correct
8 Correct 94 ms 7368 KB Output is correct
9 Correct 150 ms 7004 KB Output is correct
10 Correct 30 ms 7416 KB Output is correct
11 Correct 129 ms 7372 KB Output is correct
12 Correct 80 ms 7460 KB Output is correct
13 Correct 1923 ms 7180 KB Output is correct
14 Correct 85 ms 7588 KB Output is correct
15 Correct 30 ms 7456 KB Output is correct
16 Correct 30 ms 7472 KB Output is correct
17 Execution timed out 3082 ms 6196 KB Time limit exceeded
18 Halted 0 ms 0 KB -