fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int                                        long long
  4. #define TEST                                       int t; cin>>t; while(t--)
  5. #define pb                                         push_back
  6. #define pii                                        pair <int, int>
  7. #define vi                                         vector <int>
  8. #define ff                                         first
  9. #define ss                                         second
  10. #define sz(v)                                      (int)v.size()
  11. #define vpii                                       vector <pair <int, int>>
  12. #define vvi                                        vector <vector <int> >
  13. #define all(x)                                     (x).begin(), (x).end()
  14. #define rall(x)                                    (x).rbegin(), (x).rend()
  15. #define endl                                       "\n"
  16. #define MAX                                        1e18
  17. #define MIN                                        INT_MIN
  18. #define mod                                        1000000007
  19. typedef long long                                  ll;
  20.  
  21. int dp[1005][1005][2];
  22. int getAns(int a[], int s[], char c[], int used, int n, int m) {
  23.   if (n == 0 || m == 0)return 0;
  24.  
  25.   if (dp[n][m][used] != -1)return dp[n][m][used];
  26.   if (used && s[n - 1] <= m && c[n - 1] == 'S') {
  27.     return dp[n][m][1] = max(a[n - 1] + getAns(a, s, c, 1, n - 1, m - s[n - 1]), getAns(a, s, c, 1, n - 1, m));
  28.   }
  29.   if (!used && s[n - 1] <= m && c[n - 1] == 'S') {
  30.     return dp[n][m][used] = max(a[n - 1] + getAns(a, s, c, 1, n - 1, m - (s[n - 1] / 2)), max(a[n - 1] + getAns(a, s, c, 0, n - 1, m - (s[n - 1])), getAns(a, s, c, 0, n - 1, m)));
  31.   }
  32.   else {
  33.     return dp[n][m][used] = getAns(a, s, c, used, n - 1, m);
  34.   }
  35.   return dp[n][m][used];
  36. }
  37.  
  38. void solve() {
  39.   int n;
  40.   cin >> n;
  41.   int m; cin >> m;
  42.   char c[n]; int s[n], a[n];
  43.   for (int i = 0; i < n; i++) {
  44.     string st; cin >> st;
  45.     cin >> c[i] >> s[i] >> a[i];
  46.   }
  47.  
  48.   memset(dp, -1, sizeof(dp));
  49.   cout << getAns(a, s, c, 0, n, m) << endl;
  50.  
  51. }
  52. signed main()
  53. {
  54. // #ifndef ONLINE_JUDGE
  55. //   freopen("input.txt", "r", stdin);
  56. //   freopen("output.txt", "w", stdout);
  57. // #endif
  58.   mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
  59.   ios_base :: sync_with_stdio(0);
  60.   cin.tie(0);
  61.   //seive();
  62.  
  63.   //TEST
  64.   solve();
  65.  
  66. }
Success #stdin #stdout 0.01s 19344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ngH5ud
language:
C++14 (gcc 8.3)
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!