oj.uz

Submission #608824

# Submission time Handle Problem Language Result Execution time Memory
608824 2022-07-27T10:33:33 Z OttoTheDino Building Bridges (CEOI17_building) C++17
0 / 100
 33 ms 3812 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)				  for (int i = s; i <= e; ++i)
typedef long long ll;

const ll inf = 1e9, mx = 1e6;

ll seg[4*mx+1], h[mx+1], w[mx+1], dp[mx+1];

void upd (ll u, ll bl, ll br, ll id) {
	if (!seg[id]) {
		seg[id] = u;
		return;
	}
	ll mid = (bl+br)/2;
	if (dp[u]-2*h[u]*mid<dp[seg[id]]-2*h[seg[id]]*mid) swap (seg[id], u);
	if (bl==br) return;
	if (-2*h[u]<-2*h[seg[id]]) upd (u, mid+1, br, 2*id+1);
	else if (-2*h[u]>-2*h[seg[id]]) upd (u, bl, mid, 2*id);
}

ll qry (ll x, ll bl, ll br, ll id) {
	if (!seg[id]) return inf*inf;
	if (bl==br) return dp[seg[id]] - 2*h[seg[id]]*x;
	ll mid = (bl+br)/2;
	if (x<=mid) return min(dp[seg[id]]-2*h[seg[id]]*x, qry(x, bl, mid, 2*id));
	return min(dp[seg[id]]-2*h[seg[id]]*x, qry(x, bl, mid, 2*id));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll n, s = 0;
	cin >> n;

	rep (i,1,n) cin >> h[i];
	rep (i,1,n) {
		cin >> w[i];
		s += w[i];
	}

	dp[1] = h[1]*h[1]-w[1];

	upd (1, 1, mx, 1); 

	rep (i,2,n) {
		dp[i] = qry (h[i], 1, mx, 1) + h[i]*h[i] - w[i];

		if (i==n) cout << s+dp[n] << "\n";

		else {
			dp[i] += h[i]*h[i];
			upd (i, 1, mx, 1); 
		}
	}

	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -