Guest User

Untitled

a guest
Feb 14th, 2023
376
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #ifndef ONLINE_JUDGE
  4. #include "./debug.h"
  5. #else
  6. #define debug(...)
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12.  
  13. const int inf = 1e18;
  14. const int N = 1e5 + 5;
  15. const int mod = 1e9 + 7;
  16.  
  17. const vector<char> chars = {'#', '$', '%', '@', '&'};
  18.  
  19. void solve() {
  20.     map<char, int> ids;
  21.     for (int i = 0; i < 5; i++) {
  22.         ids[chars[i]] = i;
  23.     }
  24.     int n;
  25.     cin >> n;
  26.     vector<pair<string, int>> arr(n + 1);
  27.     for (int i = 1; i <= n; i++) {
  28.         cin >> arr[i].first >> arr[i].second;
  29.     }
  30.     vector<vector<int>> dp(n + 1, vector<int>(32, inf));
  31.     for (int i = 0; i <= n; i++) {
  32.         dp[i][0] = 0;
  33.     }
  34.     for (int i = 1; i <= n; i++) {
  35.         int mask = 0;
  36.         for (char c : arr[i].first) {
  37.             mask |= (1 << ids[c]);
  38.         }
  39.         for (int j = 0; j < 32; j++) {
  40.             dp[i][j] = dp[i - 1][j];
  41.         }
  42.         for (int j = 0; j < 32; j++) {
  43.             dp[i][j | mask] =
  44.                 min(min(dp[i][j | mask], (dp[i - 1][j]) + arr[i].second),
  45.                     dp[i - 1][j | mask]);
  46.         }
  47.     }
  48.     int res = inf;
  49.     for (int i = 1; i <= n; i++) {
  50.         res = min(res, dp[i][31]);
  51.     }
  52.     cout << (res == inf ? -1 : res) << "\n";
  53. }
  54.  
  55. signed main() {
  56. #ifndef ONLINE_JUDGE
  57.     freopen("input.out", "r", stdin);
  58.     freopen("output.out", "w", stdout);
  59.     freopen("error.out", "w", stderr);
  60. #endif
  61.     int T = 1;
  62.     // cin >> T;
  63.     for (int t = 1; t <= T; t++) {
  64.         // cout << "Case #" << t << ": ";
  65.         solve();
  66.     }
  67.     return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment