Diving for Gold.

Author : Jisan
Programming language : Java
Difficulty : Advance
Status : Accepted
Problem number : UVA-990
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=931

Help: http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html

Code:

import java.util.*;
public class Uva_990{
static int[] depth;
static int[] value;
static int[] T;
static int[] V;
static int[] D;
static int indx;
   public static void main(String[] args) {
Scanner in =new Scanner(System.in);
for(int jisan=0;in.hasNext();jisan=1){
if(jisan!=0)
System.out.println();
int time=in.nextInt();
int w=in.nextInt();
int n=in.nextInt();
T = new int[n];
depth=new int[n];
value=new int[n];
for(int i=0;i<n;i++){
depth[i]=in.nextInt();
value[i]=in.nextInt();
T[i]=(w*depth[i])+(2*w*depth[i]);
}
int [][] dp =new int [n+1][time+1];
for(int indx=1;indx<=n;indx++){
for(int t=1;t<=time;t++){
dp[indx][t]=dp[indx-1][t];
if(t-T[indx-1]>=0){
dp[indx][t]=Math.max(dp[indx][t],value[indx-1]+dp[indx-1][t-T[indx-1]]);

}
}
}
System.out.println(dp[n][time]);
indx=0;
D=new int[n];
V=new int[n];
printSolution(n,time,dp);
System.out.println(indx);
for(int i=0;i<n;i++){
for(int j=0;j<indx;j++){
if(D[j]==depth[i] && V[j]==value[i]){
System.out.printf("%d %d\n",depth[i],value[i]);
}
}
}
}
}
public static void printSolution(int n,int time,int[][] dp){
if(n<=0){
return;
}
if(dp[n][time]==dp[n-1][time]){
printSolution(n-1,time,dp);
}else{
if(time-T[n-1]>=0){
D[indx]=depth[n-1];
V[indx]=value[n-1];
indx++;
printSolution(n-1,time-T[n-1],dp);
}
}
}
}