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