Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "BUILDING"
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 1e5 + 5;
- constexpr ll Inf = 1e17;
- #define sz(x) (int)(x.size())
- int n;
- ll h[N], w[N], dp[N];
- ll A(int x)
- {
- return -2 * h[x];
- }
- ll B(int x)
- {
- return dp[x] - w[x] + h[x] * h[x];
- }
- ll More(int x)
- {
- return h[x] * h[x] + w[x - 1];
- }
- ld inter(int x, int y)
- {
- return (ld)1.0 * (B(x) - B(y)) / (A(y) - A(x));
- }
- struct ConvexHullTrick
- {
- vector<int> line;
- vector<ld> point;
- bool Empty;
- ConvexHullTrick()
- {
- Empty = 1;
- point.emplace_back(-Inf);
- }
- void Clear()
- {
- Empty = 1;
- line.clear();
- point.clear();
- point.emplace_back(-Inf);
- }
- void Add(int i)
- {
- while (sz(line) >= 2 || (sz(line) == 1 && A(line[0]) == A(i)))
- {
- if (A(line.back()) != A(i))
- {
- if (inter(i, line.back()) <= inter(i, line[sz(line) - 2]))
- {
- line.pop_back();
- point.pop_back();
- }
- else
- break;
- }
- else
- {
- if (B(line.back()) > B(i))
- {
- line.pop_back();
- if (!line.empty())
- point.pop_back();
- }
- else
- break;
- }
- }
- Empty = 0;
- if (line.empty() || A(line.back()) != A(i))
- {
- if (!line.empty())
- point.emplace_back(inter(i, line.back()));
- line.emplace_back(i);
- }
- }
- ll Get(int x)
- {
- if (Empty)
- return Inf;
- int j = lower_bound(point.begin(), point.end(), h[x]) - point.begin();
- //cout << line.back() << " " << j - 1 << " " << line[j - 1] << "\n";
- return A(line[j - 1]) * h[x] + B(line[j - 1]) + More(x);
- }
- } f[17];
- void Read()
- {
- 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];
- }
- }
- void Update(int x)
- {
- int pos = 0;
- vector<int> tmp({x});
- while (pos < 17 && !f[pos].Empty)
- {
- for (auto i : f[pos].line)
- tmp.emplace_back(i);
- f[pos].Clear();
- ++pos;
- }
- sort(tmp.begin(), tmp.end(), [&](const int &x, const int &y)
- { return A(x) > A(y); });
- for (auto i : tmp)
- f[pos].Add(i);
- }
- void Solve()
- {
- Update(1);
- for (int i = 2; i <= n; ++i)
- {
- dp[i] = Inf;
- for (int j = 0; j < 17; ++j)
- if (!f[j].Empty)
- {
- //cout << j << " ";
- dp[i] = min(dp[i], f[j].Get(i));
- }
- Update(i);
- //cout << i << ": " << dp[i] << "\n";
- }
- cout << dp[n];
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement