제출 #565490

#제출 시각아이디문제언어결과실행 시간메모리
565490zaneyuBuilding Bridges (CEOI17_building)C++14
100 / 100
66 ms9792 KiB
/*input 6 3 8 7 1 6 6 0 -1 9 1 2 0 */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; //order_of_key #of elements less than x // find_by_order kth element typedef long long int ll; #define ld long double #define pii pair<int,int> typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; #define f first #define s second #define pb push_back #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define FILL(n,x) memset(n,x,sizeof(n)) #define ALL(_a) _a.begin(),_a.end() #define sz(x) (int)x.size() const ll maxn=2e5+5; const ll maxlg=__lg(maxn)+2; const ll INF64=4e18; const int MOD=1e9+7; const int INF=0x3f3f3f3f; const ld PI=acos(-1); const ld eps=1e-9; #define lowb(x) x&(-x) #define MNTO(x,y) x=min(x,(__typeof__(x))y) #define MXTO(x,y) x=max(x,(__typeof__(x))y) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())+1 template<typename T1,typename T2> ostream& operator<<(ostream& out,pair<T1,T2> P){ out<<P.f<<' '<<P.s; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T> V){ REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":""); return out; } ll mult(ll a,ll b){ if(a<0) a+=MOD; return (a*b)%MOD; } ll mypow(ll a,ll b){ if(b<=0) return 1; ll res=1LL; while(b){ if(b&1) res=mult(res,a); a=mult(a,a); b>>=1; } return res; } struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { static const ll inf = LLONG_MAX; ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { k=-k,m=-m; auto z = insert({k, m, 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.k * x + l.m; } }; ll pref[maxn]; ll arr[maxn]; ll dp[maxn]; int32_t main(){ ios::sync_with_stdio(false),cin.tie(0); int n; cin>>n; REP(i,n) cin>>arr[i]; ll cur=0; REP(i,n){ int x; cin>>x; cur+=x; pref[i]=cur; } LineContainer lc; REP(i,n){ if(i) dp[i]=-lc.query(arr[i])+arr[i]*arr[i]+pref[i-1]; lc.add(-2*arr[i],dp[i]-pref[i]+arr[i]*arr[i]); } cout<<dp[n-1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...