fork download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. private static int solve(int n, int[]arr, int k){
  11. int[] dp = new int[n+1];
  12. dp[0] = 0;
  13. SortedSet<Integer> set = new TreeSet<>();
  14. set.add(0);
  15.  
  16. for(int i = 1; i<n+1; i++){
  17. dp[i] = set.first() + arr[i-1];
  18. set.add(dp[i]);
  19. if(i>k-1) set.remove(dp[i-k]);
  20. }
  21. return dp[n];
  22. }
  23. public static void main (String[] args) throws java.lang.Exception
  24. {
  25. // your code goes here
  26. Scanner sc = new Scanner(System.in);
  27. int n = sc.nextInt();
  28. int[] arr = new int[n];
  29. for(int i = 0; i<n; i++)arr[i] = sc.nextInt();
  30. int k = sc.nextInt();
  31.  
  32. System.out.println(solve(n,arr,k));
  33. }
  34. }
Success #stdin #stdout 0.15s 54712KB
stdin
5
4
3
6
3
1
2
stdout
7