fork(1) 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.         }
  71.         return //dp[numW][numBlack][numR][numBlue][i][currSpent] =
  72.                 res;
  73.     }
  74.  
  75.     int ans;
  76.  
  77.     void Case() throws IOException {
  78.         n = nextInt();
  79.         budget = nextInt();
  80.         items = new Item[n];
  81.         for (int i = 0; i < n; i++) items[i] = new Item(next(), nextInt(), nextInt(), nextInt());
  82.         dp = new int[2][4][6][6][n][budget + 1];
  83.         for (int a = 0; a <= 1; a++)
  84.             for (int i = 0; i <= 3; i++)
  85.                 for (int j = 0; j <= 5; j++)
  86.                     for (int k = 0; k <= 5; k++)
  87.                         for (int l = 0; l < n; l++)
  88.                             for (int m = 0; m <= budget; m++)
  89.                                 dp[a][i][j][k][l][m] = dp_1;
  90.         ans = go( 0,  0,  0,  0,  0,  0);
  91.         out.println(ans);
  92.         out.flush();
  93.     }
  94.  
  95.  
  96.     void solve() throws Exception {
  97.         int t = nextInt();
  98.         while (t-- > 0) Case();
  99.     }
  100.  
  101.     private int gcd(int a, int b) {
  102.         while (b > 0) {
  103.             int temp = b;
  104.             b = a % b;
  105.             a = temp;
  106.         }
  107.         return a;
  108.     }
  109.  
  110.     int min(int x, int y) {
  111.         return Integer.min(x, y);
  112.     }
  113.  
  114.     int max(int x, int y) {
  115.         return Integer.max(x, y);
  116.     }
  117.  
  118.     long min(long x, long y) {
  119.         return Long.min(x, y);
  120.     }
  121.  
  122.     long max(long x, long y) {
  123.         return Long.max(x, y);
  124.     }
  125.  
  126.     int[] sort(int[] arr) {
  127.         sort(arr, 0, arr.length - 1);
  128.         return arr;
  129.     }
  130.  
  131.     void sort(int arr[], int l, int r) {
  132.         if (l < r) {
  133.             int m = (l + r) / 2;
  134.             sort(arr, l, m);
  135.             sort(arr, m + 1, r);
  136.             merge(arr, l, m, r);
  137.         }
  138.     }
  139.  
  140.     void merge(int arr[], int l, int m, int r) {
  141.         int n1 = m - l + 1;
  142.         int n2 = r - m;
  143.         int L[] = new int[n1];
  144.         int R[] = new int[n2];
  145.         for (int i = 0; i < n1; ++i)
  146.             L[i] = arr[l + i];
  147.         for (int j = 0; j < n2; ++j)
  148.             R[j] = arr[m + 1 + j];
  149.         int i = 0, j = 0;
  150.         int k = l;
  151.         while (i < n1 && j < n2) {
  152.             if (L[i] <= R[j]) {
  153.                 arr[k] = L[i];
  154.                 i++;
  155.             } else {
  156.                 arr[k] = R[j];
  157.                 j++;
  158.             }
  159.             k++;
  160.         }
  161.         while (i < n1) {
  162.             arr[k] = L[i];
  163.             i++;
  164.             k++;
  165.         }
  166.         while (j < n2) {
  167.             arr[k] = R[j];
  168.             j++;
  169.             k++;
  170.         }
  171.     }
  172.  
  173.     class Seg implements Comparable<Seg> {
  174.         int st, end;
  175.  
  176.         public Seg(int st, int end) {
  177.             this.st = st;
  178.             this.end = end;
  179.         }
  180.  
  181.         @Override
  182.         public boolean equals(Object o) {
  183.             if (this == o) return true;
  184.             if (o == null || getClass() != o.getClass()) return false;
  185.             Seg seg = (Seg) o;
  186.             return st == seg.st &&
  187.                     end == seg.end;
  188.         }
  189.  
  190.         @Override
  191.         public int hashCode() {
  192.             return Objects.hash(st, end);
  193.         }
  194.  
  195.         @Override
  196.         public int compareTo(Seg seg) {
  197.             return st == seg.st ? Integer.compare(end, seg.end) : Integer.compare(st, seg.st);
  198.         }
  199.     }
  200.  
  201.     private int[] na(int n) throws IOException {
  202.         int[] a = new int[n];
  203.         for (int i = 0; i < n; i++) a[i] = nextInt();
  204.         return a;
  205.     }
  206.  
  207.     private long[] nal(int n) throws IOException {
  208.         long[] a = new long[n];
  209.         for (int i = 0; i < n; i++) a[i] = nextLong();
  210.         return a;
  211.     }
  212.  
  213.     int nextInt() throws IOException {
  214.         return parseInt(next());
  215.     }
  216.  
  217.     long nextLong() throws IOException {
  218.         return parseLong(next());
  219.     }
  220.  
  221.     double nextDouble() throws IOException {
  222.         return parseDouble(next());
  223.     }
  224.  
  225.     String next() throws IOException {
  226.         while (tok == null || !tok.hasMoreTokens()) {
  227.             tok = new StringTokenizer(in.readLine());
  228.         }
  229.         return tok.nextToken();
  230.     }
  231.  
  232.     public static void main(String[] args) throws Exception {
  233.         try {
  234.             if (isLocal) {
  235.                 in = new BufferedReader(new FileReader("src/tests/sol.in"));
  236.                 out = new PrintWriter(new BufferedWriter(new FileWriter("src/tests/sol.out")));
  237.             } else {
  238.                 in = new BufferedReader(new InputStreamReader(System.in));
  239.                 out = new PrintWriter(new OutputStreamWriter(System.out));
  240.             }
  241. //            long lStartTime = System.currentTimeMillis();
  242.             new Main().solve();
  243. //            long lEndTime = System.currentTimeMillis();
  244. //            out.println("Elapsed time in seconds: " + (double) (lEndTime - lStartTime) / 1000.0);
  245.             in.close();
  246.             out.close();
  247.         } catch (Throwable e) {
  248.             e.printStackTrace();
  249.             exit(1);
  250.         }
  251.     }
  252. }
  253.  
Success #stdin #stdout 0.32s 61468KB
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/aPdZjZ
language:
Java (HotSpot 12)
created:
3 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!