fork download
  1. #include<bits/stdc++.h>
  2. #define f1(i, n) for(int i=1;i<=n;++i)
  3. #define f0(i, n) for(int i=0;i<n;++i)
  4. #define ull unsigned long long
  5. #define ll long long
  6. #define rev(a) reverse(a.begin(),a.end())
  7. #define all(x) x.begin(),x.end()
  8. #define so(A, n) sort(A+1, A+n+1)
  9. using namespace std;
  10. const int maxn = 1e6 + 1;
  11. const int N = 5e5 + 1;
  12. ll A[maxn], dp[maxn];
  13. int main()
  14. {
  15. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  16. ll n, k;
  17. cin >> n >> k;
  18. f1(i, n) {
  19. cin >> A[i];
  20. }
  21. dp[1] = A[1];
  22. for (ll i = 2; i <= n; ++i) {
  23. ll ma = LLONG_MIN;
  24. for (ll j = max(i - k, 0ll); j < i; ++j) {
  25. ma = max(ma, dp[j]);
  26. }
  27. dp[i] = ma + A[i];
  28. }
  29. ll res = LLONG_MIN;
  30. for (int i = 1; i <= n; ++i) res = max(res, dp[i]);
  31. cout << res;
  32. }
  33.  
  34.  
Success #stdin #stdout 0.01s 5292KB
stdin
Standard input is empty
stdout
-9223372036854775808