fork download
copy 
  1. import java.io.IOException;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. class QBIT03
  6. {
  7.     public static void main(String[] args) throws IOException
  8.     {
  9.         Scanner sc=new Scanner(System.in);
  10.         int tc=sc.nextInt();
  11.         while(tc-->0)
  12.         {
  13.             int beginLevel=sc.nextInt(),maxLevel=sc.nextInt(),n=sc.nextInt();
  14.             int[] changeIntervals=new int[n];
  15.             for(int i=0;i<n;i++)
  16.                 changeIntervals[i]=sc.nextInt();
  17.             boolean[][] canHave = new boolean[changeIntervals.length+1][maxLevel+1];
  18.             for(int i = 0; i <= changeIntervals.length; i++)
  19.                 Arrays.fill(canHave[i], false);
  20.             canHave[0][beginLevel] = true;
  21.             for(int i = 0; i < changeIntervals.length; i++)
  22.                 for(int j = 0; j <= maxLevel; j++)
  23.                     if(canHave[i][j])
  24.                     {
  25.                         if(j + changeIntervals[i] <= maxLevel)
  26.                             canHave[i+1][j + changeIntervals[i]] = true;
  27.                         if(j - changeIntervals[i] >= 0)
  28.                             canHave[i+1][j - changeIntervals[i]] = true;
  29.                     }
  30.             int max = -1;
  31.             for(int j = 0; j <= maxLevel; j++)
  32.                 if(canHave[changeIntervals.length][j])
  33.                     max = j;
  34.             System.out.println(max);
  35.         }
  36.     }
  37. }
Success #stdin #stdout 0.15s 321344KB
comments (?)
stdin
copy 
1
5
10
3
5 3 7
stdout
copy 
10
https://ideone.com/4KaAs3
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

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!