fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. public class Main
  4. {
  5.  
  6. 	public static void main(String args[]) throws IOException
  7. 	{
  8.  
  9.                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  10.                 BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  11.                 String str[];
  12.  
  13. 		int n = Integer.parseInt(br.readLine());
  14.                 int t = Integer.parseInt(br.readLine());
  15.  
  16.                 long mark[] = new long[n+1];
  17.                 long time[] = new long[n+1];
  18.  
  19.                 long dp1[][] = new long[n+1][t+1];
  20.                 long dp2[][] = new long[n+1][t+1];
  21.  
  22.                 str = br.readLine().split(" ");
  23.                 for(int i=0 ; i<str.length ; i++)
  24.                       mark[i+1] = Integer.parseInt(str[i]);
  25.  
  26.                 str = br.readLine().split(" ");
  27.                 for(int i=0 ; i<str.length ; i++)
  28.                       time[i+1] = Integer.parseInt(str[i]);
  29.  
  30.                 for(int i=0 ; i<=n ; i++)
  31.                 {
  32.                       for(int j=0 ; j<=t ; j++)
  33.                       {
  34.                             if(i==0 || j==0)
  35.                             {
  36.                                   dp1[i][j] = 0;
  37.                                   continue;
  38.                             }
  39.  
  40.                             if(time[i] > j)
  41.                                   dp1[i][j] = dp1[i-1][j];
  42.                             else
  43.                                   dp1[i][j] = Math.max(mark[i]+dp1[i-1][j-(int)time[i]], dp1[n-1][j]);
  44.  
  45.  
  46.                       }
  47.                 }
  48.  
  49.  
  50.                 for(int i=0 ; i<=n ; i++)
  51.                 {
  52.                       for(int j=0 ; j<=t ; j++)
  53.                       {
  54.                             if(i==0 || j==0)
  55.                             {
  56.                                   dp2[i][j] = 0;
  57.                                   continue;
  58.                             }
  59.  
  60.                             if(time[i] > j)
  61.                                   dp2[i][j] = dp2[i-1][j];
  62.                             else
  63.                             {
  64.                                   long temp1 = 2*mark[i] + dp1[i-1][j-(int)time[i]];
  65.                                   long temp2 = Math.max(mark[i]+dp2[i-1][j-(int)time[i]], dp2[n-1][j]);
  66.  
  67.                                   dp2[i][j] = Math.max(temp1,temp2);
  68.                             }
  69.  
  70.                       }
  71.                 }
  72.  
  73.  
  74.                 System.out.print(dp2[n][t]);
  75. 	}
  76. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
3
10
1 2 3
4 3 4
stdout
copy 
8
https://ideone.com/dIRfG3
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!