Round A 2020 Google Kick Start Plates Problem | JAVA | Know About

Problem

Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.

What is the maximum number of houses you can buy?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, K and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.

In Sample Case #1, Dr. Patel needs to pick P = 5 plates:

He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In total, the sum of beauty values is 250.

In Sample Case #2, Dr. Patel needs to pick P = 3 plates:

He can pick the top 2 plates from the first stack (80 + 80 = 160).
He can pick no plates from the second stack.
He can pick the top plate from the third stack (20).
In total, the sum of beauty values is 180.


PROGRAM


import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int t = sc.nextInt(); for (int i = 1; i <= t; i++) { int N, K, P; N = sc.nextInt(); K = sc.nextInt(); P = sc.nextInt(); int[][] a = new int[N][K]; for (int j = 0; j < N; j++) { for (int l = 0; l < K; l++) { a[j][l] = sc.nextInt(); } } int[][] sum = new int[N + 1][K + 1]; for (int z = 1; z <= N; z++) { for (int y = 1; y <= K; y++) { sum[z][y] = sum[z][y - 1] + a[z - 1][y - 1]; } } int[][] dp = new int[N + 1][P + 1]; for (int m = 1; m <= N; m++) { for (int n = 1; n <= P; n++) { dp[m][n] = 0; for (int x = 0; x <= Math.min(n, K); x++) { dp[m][n] = Math.max(dp[m][n], sum[m][x] + dp[m - 1][n - x]); } } } System.out.printf("Case #%d: %d\n", i, dp[N][P]); } } }

Here is the link for Google KickStart Round A 2020 Allocation problem using JAVA.