SHARE
TWEET

ccc07s5

a guest Jan 20th, 2020 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. public class ccc07s5 {
  7.  
  8.     public static void main(String[] args) throws IOException {
  9.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  10.  
  11.         int t = Integer.parseInt(br.readLine());
  12.  
  13.         for (int l = 0; l < t; l++) {
  14.             StringTokenizer st = new StringTokenizer(br.readLine());
  15.             int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken()),
  16.                     w = Integer.parseInt(st.nextToken());
  17.            
  18.             int[] pins = new int[60005], psa = new int[60005];
  19.            
  20.             int dp[][] = new int[60005][505];
  21.            
  22.             for (int i = 1; i <= n; i++)
  23.                 pins[i] = Integer.parseInt(br.readLine());
  24.            
  25.             for (int i = 1; i <= n; i++)
  26.                 psa[i] = psa[i - 1] + pins[i];
  27.            
  28.             for (int i = 1; i <= n; i++) {
  29.                 for (int j = 0; j <= k; j++) {
  30.                     // throw
  31.                     dp[i + w][j + 1] = Math.max(dp[i + w][j + 1], dp[i][j] + psa[i + w - 1] - psa[i - 1]);
  32.                     // pass
  33.                     dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
  34.                 }
  35.             }
  36.             int ans = 0;
  37.             for (int a = 0; a < 60000; a++) {
  38.                 for (int b = 0; b <= k; b++) {
  39.                     ans = Math.max(ans, dp[a][b]);
  40.                 }
  41.             }
  42.             System.out.println(ans);
  43.         }
  44.     }
  45.  
  46. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top