rembocoder

Untitled

May 14th, 2023
709
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define int int64_t
  4.  
  5. using namespace std;
  6.  
  7. void relax(int& a, int b) {
  8.     a = max(a, b);
  9. }
  10.  
  11. int32_t main() {
  12.     ios_base::sync_with_stdio(false);
  13.     int n, k;
  14.     cin >> n >> k;
  15.     vector<int> a(n);
  16.     for (int i = 1; i < n - 1; i++) {
  17.         cin >> a[i];
  18.     }
  19.     vector<int> dp(n, -2e18);
  20.     dp[0] = 0;
  21.     for (int i = 1; i < n; i++) {
  22.         for (int j = 1; j <= k && j <= i; j++) {
  23.             relax(dp[i], dp[i - j] + a[i]);
  24.         }
  25.     }
  26.     cout << dp[n - 1] << '\n';
  27. }
  28.  
Advertisement
Add Comment
Please, Sign In to add comment