fork(2) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /*
  5.   DO NOT REMOVE THIS COMMENT, OR THIS CODE WILL NOT WORK.
  6. */
  7. class MyClass {
  8.  
  9.     //using DP.
  10.     public static void solve() throws Exception {
  11. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  12. 		int t = Integer.parseInt(br.readLine());
  13. 		StringBuilder sb = new StringBuilder("");
  14. 		while (t-- > 0) {
  15. 			String[] ip=br.readLine().split(" ");
  16. 			int n = Integer.parseInt(ip[0]);
  17. 			long c = Long.parseLong(ip[1]);
  18. 			long[] arr=new long[n];
  19. 			ip=br.readLine().split(" ");
  20. 			for(int i=0;i<n;i++){
  21. 				arr[i]=Long.parseLong(ip[i]);
  22. 			}
  23. 			if(c==0) sb.append("0\n");
  24. 			else{
  25. 				long[][] dp=new long[n][n];
  26. 				long min = Long.MAX_VALUE;
  27. 				for(int j=0;j<n;j++){
  28. 					for(int i=j;i>=0;i--){
  29. 						if(i==j){
  30. 							dp[i][j] = c-arr[i];
  31. 							if(dp[i][j]<0) dp[i][j] = c;
  32. 						}
  33. 						else{
  34. 							dp[i][j] = dp[i+1][j];
  35. 							if(arr[i]<=dp[i+1][j]) dp[i][j] -= arr[i];
  36. 						}
  37. 						min = Math.min(min, dp[i][j]);
  38. 						sb.append(String.format("dp[%d][%d] is %d\n",i,j,dp[i][j]));
  39. 					}
  40. 				}
  41. 				sb.append(min+"\n");
  42. 			}
  43. 		}
  44. 		System.out.print(sb.toString());
  45. 	}
  46.  
  47. 	public static void main(String[] args) throws Exception{
  48.         solve();
  49. 	} 
  50. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
2
3 28
12 14 27
4 11
3 6 7 2
stdout
copy 
dp[0][0] is 16
dp[1][1] is 14
dp[0][1] is 2
dp[2][2] is 1
dp[1][2] is 1
dp[0][2] is 1
1
dp[0][0] is 8
dp[1][1] is 5
dp[0][1] is 2
dp[2][2] is 4
dp[1][2] is 4
dp[0][2] is 1
dp[3][3] is 9
dp[2][3] is 2
dp[1][3] is 2
dp[0][3] is 2
1
https://ideone.com/ACwwSs
Placement DP
language:
Java (HotSpot 12)
created:
9 years 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!