제출 #264798

#제출 시각아이디문제언어결과실행 시간메모리
264798anubhavdharBuilding Bridges (CEOI17_building)C++14
100 / 100
156 ms9080 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define FOR(i,N) for(i=0;i<(N);++i) #define FORe(i,N) for(i=1;i<=(N);++i) #define FORr(i,a,b) for(i=(a);i<(b);++i) #define FORrev(i,N) for(i=(N);i>=0;--i) #define F0R(i,N) for(int i=0;i<(N);++i) #define F0Re(i,N) for(int i=1;i<=(N);++i) #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i) #define F0Rrev(i,N) for(int i=(N);i>=0;--i) #define all(v) (v).begin(),(v).end() #define dbgLine cerr<<" LINE : "<<__LINE__<<"\n" #define ldd long double using namespace std; const int Alp = 26; const int __PRECISION = 9; const int inf = 1e9 + 8; const ldd PI = acos(-1); const ldd EPS = 1e-7; const ll MOD = 1e9 + 7; const ll MAXN = 1e5 + 5; const ll ROOTN = 320; const ll LOGN = 18; const ll INF = 1e18 + 1022; int N; ll dp[MAXN], pre[MAXN], h[MAXN]; struct line //mx + c { mutable ll m, c, p; bool operator < (const line& o) const {return m < o.m;} bool operator < (ll x) const {return p < x;} }; struct max_CHT_black_box : multiset<line, less<>> { ll div(ll a, ll b) {return a/b - ((a^b) < 0 && a%b);} bool isect(iterator x, iterator y) { if(y == end()){x->p = INF; return false;} if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF; else x->p = div((y->c - x->c),(x->m - y->m)); return (x->p >= y->p); } void add(ll slope, ll intercept) { auto z = insert({slope, intercept, 0}), y = z++, x = y; while(isect(y, z)) z = erase(z); if(x != begin() && isect(--x, y)) isect(x, y = erase(y)); while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return (l.m * x + l.c); } }box; signed main() { /* ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); */ ll w; cin>>N; F0R(i, N) cin>>h[i]; F0R(i, N) cin>>w, pre[i] = w + ((i == 0) ? 0 : pre[i-1]); dp[0] = 0; box.add(2*h[0], (- h[0]*h[0] - dp[0] + pre[0])); F0Re(i, N-1) { dp[i] = (h[i] * h[i] + pre[i-1]) - box.query(h[i]); box.add(2*h[i], (- h[i]*h[i] - dp[i] + pre[i])); } //F0R(i, N) // cout<<"dp["<<i<<"] = "<<dp[i]<<'\n'; cout<<dp[N-1]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...