fork download
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. using namespace std;
  4. #define vt vector
  5. #define heap priority_queue
  6. #define dq deque
  7. #define maxN 100005
  8. #define maxM 5005
  9. #define pb push_back
  10. #define pf push_front
  11. #define inf 1000000007 // mod for some cases
  12. void io() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
  13. typedef long long ll;
  14. typedef pair<ll, ll> ii;
  15. //type_here
  16. ll n, m, res, cnt, d, ans, t, f[maxM][205], s[maxM][205], a[maxN], k;
  17. void solve()
  18. {
  19. cin>>n>>k;
  20. for (int i=1;i<=n;i++) cin>>a[i];
  21. f[0][1] = 0;
  22. for (int i=1;i<=n;i++)
  23. {
  24. f[i][1] = f[i-1][1] + a[i];
  25. s[i][1] = 0;
  26. }
  27. /* f[i][j] (tổng của cái dãy số tính tới hiện tại nếu chưa cắt) và s[i][j]
  28.   (là tổng từ cái phần tử trước phần tử được cắt gần nhất tới ptu đầu đã được tối ưu)*/
  29. for (int i = 2;i<=n;i++)
  30. {
  31. for (int j = 2;j<=min(i*1ll, k+1);j++)
  32. {
  33. ll no_updated = f[i-1][j] + s[i-1][j] + a[i]; // vẫn giữ nguyên, nối tiếp với đoạn lúc trước (cắt bắt đầu từ một phần tử trước đó)
  34. ll updated = round(f[i-1][j-1]/float(10))*10 + s[i-1][j-1] + a[i]; //phần tử hiện tại sẽ là phần tử đầu tiên trong đoạn cắt mới
  35. if (no_updated<=updated&&(j<=i-1))
  36. {
  37. s[i][j] = s[i-1][j];
  38. f[i][j] = f[i-1][j] + a[i];
  39. }
  40. else
  41. {
  42. s[i][j] = s[i-1][j-1] + round(f[i-1][j-1]/float(10))*10;
  43. f[i][j] = a[i];
  44. }
  45. }
  46. }
  47. res = inf;
  48. for (int i=1;i<=k+1;i++)
  49. {
  50. ll t = round(f[n][i]/float(10))*10;
  51. res = min(res, t + s[n][i]);
  52. }
  53. cout<<res<<endl;
  54. }
  55. signed main()
  56. {
  57. io();
  58. solve();
  59. return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 7708KB
stdin
5 3
5 5 5 5 5
stdout
30