fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. import static java.lang.Double.parseDouble;
  6. import static java.lang.Integer.parseInt;
  7. import static java.lang.Long.parseLong;
  8. import static java.lang.System.exit;
  9.  
  10.  
  11. public class Main {
  12.  
  13.     static BufferedReader in;
  14.     static PrintWriter out;
  15.     static StringTokenizer tok;
  16.     static boolean isLocal = false;
  17.  
  18.  
  19.     class Item {
  20.         String color;
  21.         int cost;
  22.         int value;
  23.         int id;
  24.  
  25.         public Item(String color, int cost, int value, int id) {
  26.             this.color = color;
  27.             this.cost = cost;
  28.             this.value = value;
  29.             this.id = id;
  30.         }
  31.     }
  32.  
  33.     int n, dp_1 = -1000000;
  34.     int budget;
  35.     Item[] items;
  36.  
  37.     boolean checkMax(int numW, int numBlue, int numR, int numBlack) {
  38.         return numW <= 1 && numBlue <= 5 && numR <= 5 && numBlack <= 3;
  39.     }
  40.  
  41.     boolean checkMin(int numW, int numBlue, int numR, int numBlack) {
  42.         return numW == 1 && numBlue >= 3 && numR >= 3 && numBlack >= 1;
  43.     }
  44.  
  45.     boolean canAddItem(Item item, int numW, int numBlue, int numR, int numBlack, int currSpent) {
  46.         if (item.color.equals("W")) numW++;
  47.         if (item.color.equals("Blue")) numBlue++;
  48.         if (item.color.equals("R")) numR++;
  49.         if (item.color.equals("Black")) numBlack++;
  50.         currSpent += item.cost;
  51.         return checkMax(numW, numBlue, numR, numBlack) && currSpent <= budget && numW + numBlue + numR + numBlack <= 12;
  52.     }
  53.  
  54.     int dp[][][][][][];
  55.  
  56.     int go(int i, int numW, int numBlue, int numR, int numBlack, int currSpent) {
  57.         if (n - i + numW + numBlue + numR + numBlack < 12) return -10000;
  58.         if (i == n)
  59.             return (checkMin(numW, numBlue, numR, numBlack) && numW + numBlue + numR + numBlack == 12) ? 0 : -10000;
  60.         if (dp[numW][numBlack][numR][numBlue][i][currSpent] != dp_1)
  61.             return dp[numW][numBlack][numR][numBlue][i][currSpent];
  62.         int res = -10000;
  63.         res = max(res, go((int) (i + 1), numW, numBlue, numR, numBlack, currSpent));
  64.         if (canAddItem(items[i], numW, numBlue, numR, numBlack, currSpent)) {
  65.             if (items[i].color.equals("W")) numW++;
  66.             if (items[i].color.equals("Blue")) numBlue++;
  67.             if (items[i].color.equals("R")) numR++;
  68.             if (items[i].color.equals("Black")) numBlack++;
  69.             res = max(res, items[i].value + go( i + 1, numW, numBlue, numR, numBlack, (items[i].cost + currSpent)));
  70.             if (items[i].color.equals("W")) numW--;
  71.             if (items[i].color.equals("Blue")) numBlue--;
  72.             if (items[i].color.equals("R")) numR--;
  73.             if (items[i].color.equals("Black")) numBlack--;            
  74.         }
  75.         return dp[numW][numBlack][numR][numBlue][i][currSpent] =
  76.                 res;
  77.     }
  78.  
  79.     int ans;
  80.  
  81.     void Case() throws IOException {
  82.         n = nextInt();
  83.         budget = nextInt();
  84.         items = new Item[n];
  85.         for (int i = 0; i < n; i++) items[i] = new Item(next(), nextInt(), nextInt(), nextInt());
  86.         dp = new int[2][4][6][6][n][budget + 1];
  87.         for (int a = 0; a <= 1; a++)
  88.             for (int i = 0; i <= 3; i++)
  89.                 for (int j = 0; j <= 5; j++)
  90.                     for (int k = 0; k <= 5; k++)
  91.                         for (int l = 0; l < n; l++)
  92.                             for (int m = 0; m <= budget; m++)
  93.                                 dp[a][i][j][k][l][m] = dp_1;
  94.         ans = go( 0,  0,  0,  0,  0,  0);
  95.         out.println(ans);
  96.         out.flush();
  97.     }
  98.  
  99.  
  100.     void solve() throws Exception {
  101.         int t = nextInt();
  102.         while (t-- > 0) Case();
  103.     }
  104.  
  105.     private int gcd(int a, int b) {
  106.         while (b > 0) {
  107.             int temp = b;
  108.             b = a % b;
  109.             a = temp;
  110.         }
  111.         return a;
  112.     }
  113.  
  114.     int min(int x, int y) {
  115.         return Integer.min(x, y);
  116.     }
  117.  
  118.     int max(int x, int y) {
  119.         return Integer.max(x, y);
  120.     }
  121.  
  122.     long min(long x, long y) {
  123.         return Long.min(x, y);
  124.     }
  125.  
  126.     long max(long x, long y) {
  127.         return Long.max(x, y);
  128.     }
  129.  
  130.     int[] sort(int[] arr) {
  131.         sort(arr, 0, arr.length - 1);
  132.         return arr;
  133.     }
  134.  
  135.     void sort(int arr[], int l, int r) {
  136.         if (l < r) {
  137.             int m = (l + r) / 2;
  138.             sort(arr, l, m);
  139.             sort(arr, m + 1, r);
  140.             merge(arr, l, m, r);
  141.         }
  142.     }
  143.  
  144.     void merge(int arr[], int l, int m, int r) {
  145.         int n1 = m - l + 1;
  146.         int n2 = r - m;
  147.         int L[] = new int[n1];
  148.         int R[] = new int[n2];
  149.         for (int i = 0; i < n1; ++i)
  150.             L[i] = arr[l + i];
  151.         for (int j = 0; j < n2; ++j)
  152.             R[j] = arr[m + 1 + j];
  153.         int i = 0, j = 0;
  154.         int k = l;
  155.         while (i < n1 && j < n2) {
  156.             if (L[i] <= R[j]) {
  157.                 arr[k] = L[i];
  158.                 i++;
  159.             } else {
  160.                 arr[k] = R[j];
  161.                 j++;
  162.             }
  163.             k++;
  164.         }
  165.         while (i < n1) {
  166.             arr[k] = L[i];
  167.             i++;
  168.             k++;
  169.         }
  170.         while (j < n2) {
  171.             arr[k] = R[j];
  172.             j++;
  173.             k++;
  174.         }
  175.     }
  176.  
  177.     class Seg implements Comparable<Seg> {
  178.         int st, end;
  179.  
  180.         public Seg(int st, int end) {
  181.             this.st = st;
  182.             this.end = end;
  183.         }
  184.  
  185.         @Override
  186.         public boolean equals(Object o) {
  187.             if (this == o) return true;
  188.             if (o == null || getClass() != o.getClass()) return false;
  189.             Seg seg = (Seg) o;
  190.             return st == seg.st &&
  191.                     end == seg.end;
  192.         }
  193.  
  194.         @Override
  195.         public int hashCode() {
  196.             return Objects.hash(st, end);
  197.         }
  198.  
  199.         @Override
  200.         public int compareTo(Seg seg) {
  201.             return st == seg.st ? Integer.compare(end, seg.end) : Integer.compare(st, seg.st);
  202.         }
  203.     }
  204.  
  205.     private int[] na(int n) throws IOException {
  206.         int[] a = new int[n];
  207.         for (int i = 0; i < n; i++) a[i] = nextInt();
  208.         return a;
  209.     }
  210.  
  211.     private long[] nal(int n) throws IOException {
  212.         long[] a = new long[n];
  213.         for (int i = 0; i < n; i++) a[i] = nextLong();
  214.         return a;
  215.     }
  216.  
  217.     int nextInt() throws IOException {
  218.         return parseInt(next());
  219.     }
  220.  
  221.     long nextLong() throws IOException {
  222.         return parseLong(next());
  223.     }
  224.  
  225.     double nextDouble() throws IOException {
  226.         return parseDouble(next());
  227.     }
  228.  
  229.     String next() throws IOException {
  230.         while (tok == null || !tok.hasMoreTokens()) {
  231.             tok = new StringTokenizer(in.readLine());
  232.         }
  233.         return tok.nextToken();
  234.     }
  235.  
  236.     public static void main(String[] args) throws Exception {
  237.         try {
  238.             if (isLocal) {
  239.                 in = new BufferedReader(new FileReader("src/tests/sol.in"));
  240.                 out = new PrintWriter(new BufferedWriter(new FileWriter("src/tests/sol.out")));
  241.             } else {
  242.                 in = new BufferedReader(new InputStreamReader(System.in));
  243.                 out = new PrintWriter(new OutputStreamWriter(System.out));
  244.             }
  245. //            long lStartTime = System.currentTimeMillis();
  246.             new Main().solve();
  247. //            long lEndTime = System.currentTimeMillis();
  248. //            out.println("Elapsed time in seconds: " + (double) (lEndTime - lStartTime) / 1000.0);
  249.             in.close();
  250.             out.close();
  251.         } catch (Throwable e) {
  252.             e.printStackTrace();
  253.             exit(1);
  254.         }
  255.     }
  256. }
  257.  
Success #stdin #stdout 0.19s 60292KB
comments (?)
stdin
copy 
1
20 1000
Black 52 11 1
Blue 43 8 2
Blue 72 0 3
Blue 97 0 4
W 72 14 5
R 94 10 6
R 75 15 7
Blue 110 17 8
Black 61 17 9
R 56 3 10
Black 120 2 11
R 108 15 12
R 116 13 13
R 70 3 14
Blue 118 10 15
R 97 2 16
R 40 17 17
W 76 11 18
Black 60 7 19
Blue 108 12 20
stdout
copy 
159
https://ideone.com/zohCud
language:
Java (HotSpot 12)
created:
5 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!