제출 #1123235

#제출 시각아이디문제언어결과실행 시간메모리
1123235IcelastBuilding Bridges (CEOI17_building)C++17
60 / 100
55 ms8624 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; // segment add min get, returns INF if no segment added struct Line{ ll a = 0, b = INF; }; struct Lichao { vector<Line> L; vector<ll> x; int N, m; Lichao(vector<ll> dom){ N = 1; x = dom; sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin()); m = x.size(); while(N < m) N*=2; for(int i = m; i <= N; i++){ x.push_back(INF); } for(int i = N; i >= 1; i--){ x[i] = x[i-1]; } L.resize(N*2+1, Line()); }; bool better(Line a, Line b, ll x){ return a.a*x + a.b < b.a*x + b.b; } void addline(int node, int low, int high, Line e){ int mid = (low+high)/2; bool doml = better(e, L[node], x[low]); bool domm = better(e, L[node], x[mid]); if(domm) swap(e, L[node]); if(low == high) return; if(doml != domm){ addline(node*2, low, mid, e); }else{ addline(node*2+1, mid+1, high, e); } } void add(Line e){ addline(1, 1, N, e); } ll query(ll v){ int k = lower_bound(x.begin()+1, x.end(), v) - x.begin(); k = k+N-1; ll res = INF; while(k > 0){ res = min(res, L[k].a*v + L[k].b); k /=2; } return res; } }; void solve(){ int n; cin >> n; vector<ll> h(n+1), w(n+1); for(int i = 1; i <= n; i++){ cin >> h[i]; } ll tot = 0; for(int i = 1; i <= n; i++){ cin >> w[i]; tot += w[i]; } vector<ll> dom; for(int i = 1; i <= n; i++){ dom.push_back(h[i]); } Lichao T(dom); vector<ll> f(n+1, 0); f[1] = -w[1]; T.add({-h[1]*2, f[1]+h[1]*h[1]}); for(int i = 2; i <= n; i++){ f[i] = T.query(h[i]) + h[i]*h[i] - w[i]; T.add({-h[i]*2, f[i]+h[i]*h[i]}); //cout << f[i] << " "; } cout << f[n]+tot; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen("main.inp", "r", stdin); //freopen("main.out", "w", stdout); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...