제출 #939090

#제출 시각아이디문제언어결과실행 시간메모리
939090vjudge1Building Bridges (CEOI17_building)C++17
0 / 100
69 ms3544 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(a) a.begin(), a.end() #define int long long const int N = 3e6; const int MAX = 1e16; struct Line{ int k, b; Line(int k = MAX, int b = MAX) : k(k), b(b) {} }; int F(Line &a, int x){ if(a.k == MAX && a.b == MAX) return -MAX; return -(a.k*x + a.b); } struct LiChao{ struct Node{ Line k; Node *l, *r; Node(){ l = nullptr, r = nullptr; } }; int n; Node *root; LiChao(int sz) : n(sz), root(nullptr) {} void addLine(Node *&p, int l, int r, Line &a){ if(!p) p = new Node(); int mid = (l + r) / 2; int l_side = F(a, l) > F(p->k, l); int m_side = F(a, mid) > F(p->k, mid); if(m_side) p->k = a; if(l == r-1) return; if(l_side == m_side){ addLine(p->r, mid, r, a); }else{ addLine(p->l, l, mid, a); } } void addLine(Line a){ addLine(root, -n, n, a); } int get(Node *&p, int l, int r, int x){ if(!p) return -MAX; if(l == r-1){ return F(p->k, x); } int mid = (l + r) / 2; if(mid > x){ return max(F(p->k, x), get(p->l, l, mid, x)); }else{ return max(F(p->k, x), get(p->r, mid, r, x)); } } int get(int x){ return get(root, -n, n, x); } }; /* 6 3 8 7 1 6 6 0 -1 9 1 2 0 */ signed main(){ int n; cin >> n; vector<int> h(n+1); for(int i = 1;i <= n; i++) cin >> h[i]; vector<int> w(n+1, 0); for(int i = 1;i <= n; i++){ cin >> w[i]; w[i]+= w[i-1]; } LiChao lch(N); vector<int> dp(n+1, MAX); dp[1] = 0; lch.addLine(Line(h[1], dp[1] - w[1] + h[1] * h[1])); for(int i = 2;i <= n; i++){ // kx + b /* new_dp[i] = (h[i] - h[j])^2 + dp[j] (h[i] - h[j]) * (h[i] - h[j]) = kx h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j] dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]); */ /*int ans = MAX; for(int j = 1; j < i; j++){ ans = min(ans, -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]); //dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]); } */ int mn = lch.get(-2*h[i]); mn = -mn; //cout << i << " = " << ans << " , " << mn + h[i] * h[i] + w[i-1] << '\n'; dp[i] = min(dp[i], mn + h[i]*h[i] + w[i-1]); lch.addLine(Line(h[i], dp[i] - w[i] + h[i] * h[i])); } cout << dp[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...