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.  
  25. // init
  26. void init() {
  27.     for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];
  28.     memset(dp, 0x3f, (n + 5) * sizeof(ll));
  29.     dp[0] = 0;
  30. }
  31.  
  32. // inp
  33. void inp() {
  34.     cin >> n >> k;
  35.     for (int i = 1; i <= n; i++) cin >> a[i];
  36. }
  37.  
  38. // proc
  39. ll cost(int l, int r) {
  40.     int mid = (l + r) / 2;
  41.     return 1ll * (mid - l + 1) * a[mid] - (pref[mid] - pref[l - 1]) + (pref[r] - pref[mid]) - 1ll * (r - (mid + 1) + 1) * a[mid] + k;
  42. }
  43.  
  44. void dnc(int l, int r, int optl, int optr) {
  45.     if (l > r) return;
  46.     int mid = (l + r) / 2;
  47.     dnc(l, mid - 1, optl, optr);
  48.     int opt = 0;
  49.     for (int j = optl; j <= min(optr, mid - 1); j++) {
  50.         if (mini(dp[mid], dp[j] + cost(j + 1, mid))) opt = j;
  51.     }
  52.     dnc(mid + 1, r, opt, optr);
  53. }
  54.  
  55. void proc() {
  56.     dnc(1, n, 0, n);
  57.     cout << dp[n];
  58. }
  59.  
  60. signed main() {
  61.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62.     if (fopen(file".inp", "r")) {
  63.         freopen(file".inp", "r", stdin);
  64.         freopen(file".out", "w", stdout);
  65.     }
  66.  
  67.     inp();
  68.     init();
  69.     proc();
  70.     cerr << "Time elapsed: " << TIME << "s.\n";
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 0.00449s.
https://ideone.com/ojCUyc
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!