Guest User

Untitled

a guest
Feb 8th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.46 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. import static java.lang.Integer.max;
  7.  
  8. /**
  9.  * Created by bugkiller on 07/02/18.
  10.  */
  11. public class CalvinsGame {
  12.  
  13.     static int a[] = new int[1000005];
  14.     static int dp[] = new int[1000005];
  15.  
  16.     public static void main(String[] args) throws IOException {
  17.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  18.         int n, k;
  19.         String[] s;
  20.         s = br.readLine().split("\\s");
  21.         n = Integer.parseInt(s[0]);
  22.         k = Integer.parseInt(s[1]);
  23.         s = br.readLine().split("\\s");
  24.         for (int i = 1; i <= n; i++) {
  25.             a[i] = Integer.parseInt(s[i - 1]);
  26.         }
  27.         System.out.println(solve(a, n, k));
  28.     }
  29.  
  30.     private static int solve(int[] a, int n, int k) {
  31.         return maxScore(a, n, k);
  32.     }
  33.  
  34.     private static int maxScore(int[] a, int n, int k) {
  35.         for (int i = k+1; i <=n ; i++) {
  36.             dp[i] = max(dp[i - 1], dp[i - 2]) + a[i];
  37.         }
  38.         int maxScore = 0, maxScoreIndex = k;
  39.         for (int i = k; i <=n; i++) {
  40.             if (dp[i] > maxScore) {
  41.                 maxScore = dp[i];
  42.                 maxScoreIndex = i;
  43.             }
  44.         }
  45.         Arrays.fill(dp, 0);
  46.         for (int i = maxScoreIndex - 1; i > 0; i--) {
  47.             dp[i] = max(dp[i + 1], dp[i + 2]) + a[i];
  48.         }
  49.         return dp[1] + maxScore;
  50.     }
  51. }
Add Comment
Please, Sign In to add comment