Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define cerr if (false) cerr
- #define int long long
- const int inf = 1e18 + 239;
- namespace LeeChaoTree {
- struct Line {
- int k;
- int b;
- Line() {
- k = 0;
- b = -inf;
- }
- Line(int k_, int b_) {
- k = k_;
- b = b_;
- }
- int get_val(int x) {
- return k * x + b;
- }
- };
- int sz;
- vector<Line> t;
- void modify(int v, int l, int r, Line to) {
- int m = (r + l) >> 1;
- int lp = (to.get_val(l) > t[v].get_val(l));
- int rp = (to.get_val(m) > t[v].get_val(m));
- if (rp) {
- swap(t[v], to);
- }
- if (l + 1 == r) {
- return;
- }
- if (lp != rp) {
- modify(2 * v + 1, l, m, to);
- } else {
- modify(2 * v + 2, m, r, to);
- }
- }
- int query(int v, int l, int r, int pos) {
- if (l + 1 == r) {
- return t[v].get_val(pos);
- } else {
- int m = (r + l) >> 1;
- int cur = t[v].get_val(pos);
- int qr = inf;
- if (pos < m) {
- qr = query(2 * v + 1, l, m, pos);
- } else {
- qr = query(2 * v + 2, m, r, pos);
- }
- return max(cur, qr);
- }
- }
- void add_line(int k, int b) {
- cerr << "LINE " << k << ' ' << b << '\n';
- Line to = Line(k, b);
- modify(0, 0, sz, to);
- }
- int get_val(int x) {
- return query(0, 0, sz, x);
- }
- void build(int sz_) {
- sz = sz_;
- t.resize(4 * sz);
- }
- // vector<Line> t;
- //
- // void add_line(int k, int b) {
- // cerr << "LINE " << k << ' ' << b << '\n';
- // Line to = Line(k, b);
- // t.push_back(to);
- // }
- //
- // int get_val(int x) {
- // int best = -inf;
- // for (auto y : t) {
- // best = max(best, y.get_val(x));
- // }
- // return best;
- // }
- //
- // void build(int sz_) {
- //
- // }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- //dp[i] - в момент i(i не приняли)
- //dp[i], приняли j
- //dp[i] = dp[j] + a[j] - b[j] * (i - j)
- //dp[i] = dp[j] + a[j] - b[j] * i + b[j] * j
- //dp[i] = - i * (b[j]) + (dp[j] + a[j] + b[j] * j)
- //k = - b[j], b = dp[j] + a[j] + b[j] * j
- int n;
- cin >> n;
- vector<int> a(n);
- vector<int> d(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i] >> d[i];
- }
- vector<int> dp(n + 1);
- dp[0] = 0;
- LeeChaoTree::build(n + 1);
- LeeChaoTree::add_line(-d[0], dp[0] + a[0] + d[0] * 0);
- for (int i = 1; i <= n; i++) {
- auto val = LeeChaoTree::get_val(i);
- dp[i] = max((int)0, val);
- if (i < n) {
- LeeChaoTree::add_line(-d[i], dp[i] + a[i] + d[i] * i);
- }
- }
- for (int i = 0; i <= n; i++) {
- cerr << dp[i] << ' ';
- }
- cout << dp[n];
- // vector<int> dp(n + 1);
- // dp[0] = 0;
- // for (int i = 1; i <= n; i++) {
- // for (int j = 0; j < i; j++) {
- // dp[i] = max(dp[i], - i * (d[j]) + (dp[j] + a[j] + d[j] * j));
- // }
- // }
- // for (int i = 0; i <= n; i++) {
- // cerr << dp[i] << ' ';
- // }
- // cout << dp[n];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement