| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 173142 | dvdg6566 | Building Bridges (CEOI17_building) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ld> vi;
typedef pair<ld,ld> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define All(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
typedef ll ftype;
typedef complex<ftype> point;
#define x real
#define y imag
ftype dot (point a, point b){
return (conj(a)*b).x();
}
ftype f(point a, ftype x){
return dot(a, {x,1});
}
const ll MAXN = 1e6+10;
const ll MAXV = 1LLe18;
map<int, point> line;
void add_line(point nw, ll v=1, ll l=-MAXV, ll r=MAXV){
ll m=(l+r)/2;
bool lef = f(nw, l) < f(line[v], l);
bool mid = f(nw, m) < f(line[v], m);
if (mid){
swap(line[v], nw);
}
if (r-l == 1)return;
if (lef != mid)add_line(nw,2*v,l,m);
else add_line(nw, 2*v+1, m, r);
}
ll get(ll x, ll v=1, ll l=-MAXV, ll r=MAXV){
ll t = f(line[v], x);
if (line[v].x() == 0 && line[v].y() == 0)t = 1LLe15;
// cout<<line[v].x()<<' '<<line[v].y()<<' '<<f(line[v],x)<<'\n';
ll m=(l+r)/2;
if (r-l == 1)return t;
if (x<m)return min(t, get(x, 2*v, l, m));
else return min(t, get(x,2*v+1,m,r));
}
ll N,H[MAXN], E[MAXN];
ll W;
ll dp[MAXN];
ll d[MAXN];
int main(){
cin>>N;
for (ll i=1;i<=N;++i)cin>>H[i];
for (ll i=1;i<=N;++i)cin>>E[i], W += E[i];
dp[1] = -E[1];
add_line({-2*H[1], dp[1] + H[1] * H[1]});
// cout<<dp[1] + H[1] * H[1]<<' '<<-2*H[1]<<'\n';
// return 0;
for (ll i=2;i<=N;++i){
dp[i] = H[i] * H[i] - E[i] + get(H[i]);
add_line({-2*H[i], H[i] * H[i] + dp[i]});
// return 0;
}
d[1] = -E[1];
for (int i=2;i<=N;++i){
d[i] = 1e15;
for (int j=1;j<i;++j){
d[i] = min(d[i], d[j] + (H[j] - H[i]) * (H[j] - H[i]) - E[i]);
}
// cout<<d[i]<<' '<<dp[i]<<'\n';
assert(d[i] == dp[i]);
}
}