oj.uz

Submission #444027

# Submission time Handle Problem Language Result Execution time Memory
444027 2021-07-13T02:58:21 Z penguinhacker Building Bridges (CEOI17_building) C++14
100 / 100
 83 ms 8156 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
const ll INF=1e18;
int n, h[mxN], w[mxN];

struct Line {
	ll m, b;
	mutable ll p;
	bool operator<(const Line& o) const { return m>o.m; }
	bool operator<(ll x) const { return p<x; }
};

set<Line, less<>> s;

ll ix(set<Line>::iterator l1, set<Line>::iterator l2) {
	assert(l1->m>l2->m);
	ll x=l2->b-l1->b, y=l1->m-l2->m;
	return x>=0?(x+y-1)/y:x/y;
}

bool bad(set<Line>::iterator it) {
	assert(it!=s.end());
	return it!=s.begin()&&next(it)!=s.end()&&ix(it, next(it))<=ix(prev(it), it);
}

void ins(ll m, ll b) {
	Line cur={m, b};
	auto it=s.lower_bound(cur);
	if (it!=s.end()&&it->m==m) {
		if (it->b<=b)
			return;
		it=s.erase(it);
	}
	it=s.insert(it, cur);
	if (bad(it)) {
		s.erase(it);
		return;
	}
	while(it!=s.begin()&&bad(prev(it))) s.erase(prev(it));
	while(next(it)!=s.end()&&bad(next(it))) s.erase(next(it));
	it->p=it==s.begin()?-INF:ix(prev(it), it);
	if (next(it)!=s.end())
		next(it)->p=ix(it, next(it));
}

ll qry(ll x) {
	auto it=s.lower_bound(x);
	if (it==s.end()||it->p>x) {
		assert(it!=s.begin());
		--it;
	}
	return it->m*x+it->b;
}

ll sq(int i) {
	return (ll)h[i]*h[i];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> h[i];
	for (int i=0; i<n; ++i)
		cin >> w[i];
	ins(-2*h[0], sq(0));
	for (int i=1; i<n-1; ++i) {
		ll dp=qry(h[i])-w[i]+sq(i);
		ins(-2*h[i], dp+sq(i));
	}
	ll ans=qry(h[n-1])+sq(n-1);
	cout << ans+accumulate(w+1, w+n-1, 0ll);
	return 0;
}

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 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1136 KB Output is correct
2 Correct 77 ms 2124 KB Output is correct
3 Correct 77 ms 2156 KB Output is correct
4 Correct 61 ms 2040 KB Output is correct
5 Correct 63 ms 3140 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 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 64 ms 1136 KB Output is correct
7 Correct 77 ms 2124 KB Output is correct
8 Correct 77 ms 2156 KB Output is correct
9 Correct 61 ms 2040 KB Output is correct
10 Correct 63 ms 3140 KB Output is correct
11 Correct 60 ms 2252 KB Output is correct
12 Correct 69 ms 2116 KB Output is correct
13 Correct 53 ms 2200 KB Output is correct
14 Correct 66 ms 2244 KB Output is correct
15 Correct 83 ms 8156 KB Output is correct
16 Correct 63 ms 3184 KB Output is correct
17 Correct 20 ms 2180 KB Output is correct
18 Correct 21 ms 2104 KB Output is correct