fork download
copy 
  1. // TranThienPhuc2657
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define file "lehoi"
  5. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  6. #define ll long long
  7. #define pb push_back
  8. #define fi first
  9. #define se second
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define ld long double
  13. #define Sz(x) ((int) (x).size())
  14. #define getBit(mask, i) (((mask) >> (i)) & 1)
  15. template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
  16. template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
  17. const int inf = 2e9 + 7;
  18. const ll linf = 1e18l + 7;
  19. const int mod = 1e9 + 7;
  20. const int N = 2e5 + 5;
  21.  
  22. int n, k, a[N];
  23. ll pref[N], dp[N];
  24. struct Item {
  25.     int l, r, opt;
  26. };
  27.  
  28. // init
  29. void init() {
  30.     for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];
  31.     memset(dp, 0x3f, (n + 5) * sizeof(ll));
  32.     dp[0] = 0;
  33. }
  34.  
  35. // inp
  36. void inp() {
  37.     cin >> n >> k;
  38.     for (int i = 1; i <= n; i++) cin >> a[i];
  39. }
  40.  
  41. // proc
  42. ll cost(int l, int r) {
  43.     int mid = (l + r) / 2;
  44.     return 1ll * (mid - l + 1) * a[mid] - (pref[mid] - pref[l - 1]) + (pref[r] - pref[mid]) - 1ll * (r - (mid + 1) + 1) * a[mid] + k;
  45. }
  46.  
  47. void proc() {
  48.     deque <Item> dq; dq.pb({1, n, 0});
  49.     for (int i = 1; i <= n; i++) {
  50.         Item &cur = dq.front();
  51.         dp[i] = dp[cur.opt] + cost(cur.opt + 1, i);
  52.         cur.l++;
  53.         if (cur.l > cur.r) dq.pop_front();
  54.  
  55.         while (!dq.empty() and dp[i] + cost(i + 1, dq.back().l) < dp[dq.back().opt] + cost(dq.back().opt + 1, dq.back().l)) dq.pop_back();
  56.         if (dq.empty()) dq.pb({i + 1, n, i});
  57.         else {
  58.             int l = dq.back().l, r = dq.back().r, opt = dq.back().opt;
  59.             while (l <= r) {
  60.                 int mid = (l + r) / 2;
  61.                 if (dp[i] + cost(i + 1, mid) < dp[opt] + cost(opt + 1, mid)) r = mid - 1;
  62.                 else l = mid + 1;
  63.             }
  64.             if (l <= n) {
  65.                 dq.back().r = r;
  66.                 dq.pb({l, n, i});
  67.             }
  68.         }
  69.     }
  70.     cout << dp[n];
  71. }
  72.  
  73. signed main() {
  74.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  75.     if (fopen(file".inp", "r")) {
  76.         freopen(file".inp", "r", stdin);
  77.         freopen(file".out", "w", stdout);
  78.     }
  79.  
  80.     inp();
  81.     init();
  82.     proc();
  83.     cerr << "Time elapsed: " << TIME << "s.\n";
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout #stderr 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 0.00408s.
https://ideone.com/NsLk2a
language:
C++14 (gcc 8.3)
created:
19 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!