Submission #1024168

#TimeUsernameProblemLanguageResultExecution timeMemory
1024168_callmelucianBuilding Bridges (CEOI17_building)C++14
100 / 100
56 ms19564 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) struct line { ll a, b; line() : a(0), b(0) {} line (ll a, ll b) : a(a), b(b) {} ll calc (ll x) { return a * x + b; } ll slope() { return a; } }; struct liChao { vector<line> tr; liChao() {} liChao (int sz) : tr(sz + 1, line(0, LLONG_MAX)) {} void update (line f, int l, int r) { if (l > r) return; int mid = (l + r) >> 1; if (l == r) { tr[mid] = (f.calc(l) < tr[mid].calc(l) ? f : tr[mid]); return; } if (f.calc(mid) < tr[mid].calc(mid)) swap(tr[mid], f); if (f.slope() > tr[mid].slope()) update(f, l, mid - 1); // case 1.1 if (f.slope() < tr[mid].slope()) update(f, mid + 1, r); // case 1.2 } ll query (int p, int l, int r) { int mid = (l + r) >> 1; ll cur = tr[mid].calc(p); if (p == mid) return cur; if (p < mid) return min(query(p, l, mid - 1), cur); if (p > mid) return min(query(p, mid + 1, r), cur); } }; const int M = 1e6 + 1; ll dp[M], h[M], w[M]; ll f1 (int k) { return -2 * h[k]; } ll f2 (int k) { return dp[k] + h[k] * h[k] - w[k]; } ll f3 (int k) { return h[k] * h[k] + w[k - 1]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> h[i]; for (int i = 1; i <= n; i++) { cin >> w[i]; w[i] += w[i - 1]; } liChao tree(M); tree.update(line(f1(1), f2(1)), 0, M); for (int i = 2; i <= n; i++) { dp[i] = tree.query(h[i], 0, M) + f3(i); tree.update(line(f1(i), f2(i)), 0, M); } cout << dp[n]; return 0; }

Compilation message (stderr)

building.cpp: In member function 'll liChao::query(int, int, int)':
building.cpp:50:5: warning: control reaches end of non-void function [-Wreturn-type]
   50 |     }
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...