fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define int long long
  4. #define f first
  5. #define s second
  6. #define file(a) freopen(a".INP","r",stdin);freopen(a".OUT","w",stdout);
  7. #define fastoi ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  8. #define TIME cerr << "\n\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
  9. #define ii pair<ll,ll>
  10. using namespace std;
  11. const int maxn = 1e6+5;
  12. const int MOD = 1e9+7;
  13. ll n,k,a[maxn],dp[maxn],ans=0,cnt=0,l,r,m;
  14. int32_t main()
  15. {
  16.     fastoi;
  17.     file("NASA");
  18.     cin >> n >> m;
  19.     for (int i=1;i<=n;i++) cin >> a[i];
  20.  
  21.     deque<ll> dq;
  22.     dp[1] = a[1];
  23.     dq.push_back(1);
  24.     for (int i=2;i<=n;i++)
  25.     {
  26.         if (!dq.empty() && i-m > dq.front()) dq.pop_front();
  27.         if (!dq.empty()) dp[i] = a[i] + dp[dq.front()];
  28.         else dp[i] = 1e18;
  29.         while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
  30.         dq.push_back(i);
  31.  
  32.     }
  33.     ans = 1e18;
  34.     for (int i=max(1ll,n-m+1);i<=n;i++) ans = min(ans,dp[i]);
  35.     cout << ans;
  36.     TIME;
  37.     return 0;
  38. }
  39. //─────────────────────────────────────────────────────────
  40. //─██████──██████─██████████─██████████████─██████──██████─
  41. //─██░░██──██░░██─██░░░░░░██─██░░░░░░░░░░██─██░░██──██░░██─
  42. //─██░░██──██░░██─████░░████─██░░██████████─██░░██──██░░██─
  43. //─██░░██──██░░██───██░░██───██░░██─────────██░░██──██░░██─
  44. //─██░░██████░░██───██░░██───██░░██████████─██░░██──██░░██─
  45. //─██░░░░░░░░░░██───██░░██───██░░░░░░░░░░██─██░░██──██░░██─
  46. //─██░░██████░░██───██░░██───██░░██████████─██░░██──██░░██─
  47. //─██░░██──██░░██───██░░██───██░░██─────────██░░██──██░░██─
  48. //─██░░██──██░░██─████░░████─██░░██████████─██░░██████░░██─
  49. //─██░░██──██░░██─██░░░░░░██─██░░░░░░░░░░██─██░░░░░░░░░░██─
  50. //─██████──██████─██████████─██████████████─██████████████─
  51. //─────────────────────────────────────────────────────────
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 

6.223 ms
https://ideone.com/7GtWp8
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!