fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int M = 1e9 + 7;
  5.  
  6. // Microsoft OA 21 Aug
  7.  
  8. int main()
  9. {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.  
  13.     int n, k;
  14.     cin >> n >> k;
  15.     vector<int> v(n);
  16.     for (int i = 0; i < n; i++)
  17.         cin >> v[i];
  18.     multiset<int> st;
  19.     st.insert(0);
  20.     vector<int> dp(n);
  21.     for (int i = 1; i < n; i++)
  22.     {
  23.         int mi = *st.begin();
  24.         dp[i] = v[i] + mi;
  25.         st.insert(dp[i]);
  26.         if (st.size() > k)
  27.         {
  28.             auto it = st.find(dp[i - k]);
  29.             st.erase(it);
  30.         }
  31.     }
  32.  
  33.     cout << dp[n - 1] << endl;
  34.     return 0;
  35. }
  36.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5 2
1 1 1 1 2
stdout
copy 
3
https://ideone.com/j9ZAMv
language:
C++14 (gcc 8.3)
created:
13 days 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!