Advertisement
Guest User

Untitled

a guest
May 17th, 2017
406
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 505;
  5.  
  6. struct TYPE_OF_BET {
  7.     struct Bet {
  8.         int a, b, c;
  9.         Bet(int a, int b): a(a), b(b), c(a + b) {}
  10.     };
  11.     vector<Bet> bets;
  12.     void add(int a, int b) {
  13.         bets.push_back(Bet(a,b));
  14.     }
  15.     vector<int> d[2];
  16.     int t, nt;
  17.     void calcDP() {
  18.         d[0].resize(2*N*N);
  19.         d[1].resize(2*N*N);
  20.         t = 0, nt = 1;
  21.         for(Bet bet : bets) {
  22.             for(int x = 0; x < 2 * N * N; ++x) {
  23.                 d[nt][x] = max(d[t][x], x - bet.c >= 0 ? d[t][x - bet.c] + bet.b : 0);
  24.             }
  25.             swap(t, nt);
  26.         }
  27.     }
  28.     int get(int x) {
  29.         return d[t].at(x);
  30.     }
  31. } A[3];
  32.  
  33. void solve() {
  34.     int n;
  35.     scanf("%d\n",&n);
  36.     for(int a, b, i = 0; i < n; ++i) {
  37.         char t;
  38.         scanf("%c %d %d\n",&t,&a,&b);
  39.         if ( t == 'L' ) A[0].add(a, b);
  40.         if ( t == 'W' ) A[1].add(a, b);
  41.         if ( t == 'D' ) A[2].add(a, b);
  42.     }
  43.     for(int i = 0; i < 3; ++i) {
  44.         A[i].calcDP();
  45.     }
  46.     int best = 0;
  47.     for(int x = 0; x < 2 * N * N; ++x) {
  48.         best = max(best, A[0].get(x) + A[1].get(x) + A[2].get(x) - x);
  49.     }
  50.     printf("%d\n", best);
  51. }
  52.  
  53. int main() {
  54.     solve();
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement