oj.uz

Submission #49306

# Submission time Handle Problem Language Result Execution time Memory
49306 2018-05-25T11:38:14 Z tmwilliamlin168 Building Bridges (CEOI17_building) C++14
100 / 100
 102 ms 47556 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second

const int mxN=1e5, mxH=1e6, sts=1<<21;
int n;
ll h[mxN], pw[mxN+1];
pll st[sts];

void upd(pll nl, int i=1, int l=0, int r=mxH) {
//	if(i==1)
//		cout << nl.fi << " " << nl.se << endl;
	int m=(l+r)/2;
	if(nl.fi*m+nl.se<st[i].fi*m+st[i].se)
		swap(nl, st[i]);
	if(l==r)
		return;
	if(nl.fi*l+nl.se<st[i].fi*l+st[i].se)
		upd(nl, 2*i, l, m);
	else
		upd(nl, 2*i+1, m+1, r);
}

ll qry(int x, int i=1, int l=0, int r=mxH) {
	int m=(l+r)/2;
	ll s=st[i].fi*x+st[i].se;
	if(l<r) {
		if(x<=m)
			s=min(qry(x, 2*i, l, m), s);
		else
			s=min(qry(x, 2*i+1, m+1, r), s);
	}
//	cout << x << " " << s << " " << l << " " << r << endl;
	return s;
}

int main() {
	ios_base::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 >> pw[i+1], pw[i+1]+=pw[i];
	for(int i=1; i<sts; ++i)
		st[i]={-2*h[0], h[0]*h[0]-pw[1]};
	for(int i=1; i<n; ++i) {
		ll dp=h[i]*h[i]+pw[i]+qry(h[i]);
//		cout << qry(h[i]) << " ";
		upd({-2*h[i], dp-pw[i+1]+h[i]*h[i]});
		if(i==n-1)
			cout << dp;
//		cout << endl;
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33144 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 27 ms 33308 KB Output is correct
4 Correct 27 ms 33308 KB Output is correct
5 Correct 25 ms 33540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 34916 KB Output is correct
2 Correct 85 ms 35960 KB Output is correct
3 Correct 74 ms 37168 KB Output is correct
4 Correct 71 ms 38096 KB Output is correct
5 Correct 73 ms 39040 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33144 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 27 ms 33308 KB Output is correct
4 Correct 27 ms 33308 KB Output is correct
5 Correct 25 ms 33540 KB Output is correct
6 Correct 74 ms 34916 KB Output is correct
7 Correct 85 ms 35960 KB Output is correct
8 Correct 74 ms 37168 KB Output is correct
9 Correct 71 ms 38096 KB Output is correct
10 Correct 73 ms 39040 KB Output is correct
11 Correct 98 ms 40248 KB Output is correct
12 Correct 101 ms 41232 KB Output is correct
13 Correct 83 ms 42384 KB Output is correct
14 Correct 102 ms 43764 KB Output is correct
15 Correct 75 ms 44436 KB Output is correct
16 Correct 75 ms 45420 KB Output is correct
17 Correct 70 ms 46432 KB Output is correct
18 Correct 65 ms 47556 KB Output is correct