fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <limits>
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. // A value to represent an impossible (unreachable) state.
  9. const ll NEG_INF = -1e18;
  10.  
  11. int main(){
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     int t;
  16.     cin >> t;
  17.     while(t--){
  18.         int n, k;
  19.         cin >> n >> k;
  20.         vector<ll> d(n);
  21.         for (int i = 0; i < n; i++){
  22.             cin >> d[i];
  23.         }
  24.  
  25.         // We'll use a 1D dp array for the current minute, indexed by "r" (pending sushi).
  26.         // The maximum r at minute i is at most (n - i) (since you cannot have more pending pieces than minutes remaining to eat them).
  27.         vector<ll> dp(n+1, NEG_INF), next_dp(n+1, NEG_INF);
  28.         dp[0] = 0;
  29.  
  30.         for (int i = 0; i < n; i++){
  31.             // Clear next_dp.
  32.             fill(next_dp.begin(), next_dp.end(), NEG_INF);
  33.             int rem = n - i - 1; // minutes left after minute i
  34.             for (int r = 0; r <= rem + k; r++){
  35.                 if(dp[r] == NEG_INF) continue;
  36.                 ll cur = dp[r];
  37.                 // Option 1: Do nothing.
  38.                 if(r <= rem)
  39.                     next_dp[r] = max(next_dp[r], cur);
  40.  
  41.                 // Option 2: Eat one piece (only if pending > 0).
  42.                 if(r > 0 && (r - 1) <= rem)
  43.                     next_dp[r - 1] = max(next_dp[r - 1], cur);
  44.  
  45.                 // Option 3: Take the plate delivered at minute i.
  46.                 // Only possible if after adding k pieces, pending does not exceed the remaining minutes.
  47.                 if(r + k <= rem)
  48.                     next_dp[r + k] = max(next_dp[r + k], cur + d[i]);
  49.             }
  50.             dp.swap(next_dp);
  51.         }
  52.  
  53.         cout << dp[0] << "\n";
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
5
5 2
3 6 4 1 2
7 1
3 1 4 1 5 9 2
4 3
4 3 2 1
6 2
1 3 5 2 4 6
6 1
1000000000 1 1000000000 1 1000000000 1
stdout
copy 
6
16
4
6
3000000000
https://ideone.com/ypmLFM
language:
C++ (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!