Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int main() {
- int n;
- scanf("%d", &n);
- vector<pair<ll, ll>> in;
- for (int i = 0,a,b; i < n; i++) {
- scanf("%d %d", &a, &b);
- in.push_back({a, b});
- }
- sort(in.begin(), in.end());
- vector<pair<ll, ll>> v;
- for (auto p : in) {
- while (!v.empty() && p.second >= v.back().second)
- v.pop_back();
- v.push_back(p);
- }
- n = v.size();
- vector<ll> dp;
- dp.push_back(v[0].first * v[0].second);
- vector<pair<int, int>> opt;
- opt.push_back({0, 1});
- int curOpt = 0;
- // i >= a >= b
- auto isbetter = [&v, &dp](int a, int b, int i) {
- ll dpa = v[i].first * v[a].second + (a > 0 ? dp[a-1] : 0);
- ll dpb = v[i].first * v[b].second + (b > 0 ? dp[b-1] : 0);
- return dpa <= dpb;
- };
- for (int i = 1; i < n; i++) {
- if (curOpt+1 < opt.size() && i >= opt[curOpt+1].second)
- curOpt++;
- int j = opt[curOpt].first;
- dp.push_back(min(v[i].first * v[j].second + (j > 0 ? dp[j-1] : 0),
- v[i].first * v[i].second + dp[i-1]));
- while (!opt.empty() && opt.back().second >= i && isbetter(i, opt.back().first, opt.back().second))
- opt.pop_back();
- if (!opt.empty()) {
- int l = opt.back().second, r = n-1;
- if (!isbetter(i, opt.back().first, r))
- continue;
- while (l < r) {
- int m = (l + r) >> 1;
- if (isbetter(i, opt.back().first, m)) r = m;
- else l = m+1;
- }
- opt.push_back({i, l});
- } else {
- opt.push_back({i, i+1});
- }
- }
- printf("%lld\n", dp.back());
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement