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.     ll mn = linf; int opt = 0; 
  48.     for (int j = optl; j <= min(optr, mid - 1); j++) {
  49.         if (mini(mn, dp[j] + cost(j + 1, mid))) opt = j;
  50.     }
  51.     mini(dp[mid], mn);
  52.     dnc(l, mid - 1, optl, opt);
  53.     dnc(mid + 1, r, opt, optr);
  54. }
  55.  
  56. // DNC Chen Danqi
  57. // Do la da ton tai mot cai da thoa roi nen la chi can viec 
  58. // Dua tu trai sang phai
  59. // Tinh bai toan phai tren gioi han trai, sau khi tinh xong 
  60. // Se co cai dau tien cua phai da hoan thien, khi nay thi tiep tuc lap lai nhu tren
  61. void cdq(int l, int r) {
  62.     if (l == r) return;
  63.     int mid = (l + r) / 2;
  64.     cdq(l, mid);
  65.     dnc(mid + 1, r, l, mid);
  66.     cdq(mid + 1, r);
  67. }
  68.  
  69. void proc() {
  70.     cdq(0, n);
  71.     cout << dp[n];
  72. }
  73.  
  74. signed main() {
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.     if (fopen(file".inp", "r")) {
  77.         freopen(file".inp", "r", stdin);
  78.         freopen(file".out", "w", stdout);
  79.     }
  80.  
  81.     inp();
  82.     init();
  83.     proc();
  84.     cerr << "Time elapsed: " << TIME << "s.\n";
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout #stderr 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 0.004183s.
https://ideone.com/kxiWwX
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!