Advertisement
Imran1107048

E - Regular Bracket Sequence

Oct 30th, 2020
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define endl "\n"
  6. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7.  
  8. void solve();
  9. int32_t main()
  10. {
  11. IOS;
  12. cout << fixed << setprecision(10);
  13. int _ = 1;
  14. cin >> _;
  15. while(_--) solve();
  16. return 0;
  17. }
  18.  
  19. void solve()
  20. {
  21. int n,a,b;
  22. cin >> n >> a >> b;
  23. string s;
  24. cin >> s;
  25. int f=0, e=0;
  26. for(int i=0;i<n;i++){
  27. if(s[i] == '(')
  28. f++;
  29. else
  30. e++;
  31. }
  32.  
  33. if(f==n || e==n){
  34. cout << n*a << endl;
  35. return;
  36. }
  37. int m = n;
  38. for(int i=0;i<m;){
  39. if(s[i] == '(' && s[i+1] == ')'){
  40. s.erase(i,2);
  41. m--;
  42. if(i>0)
  43. i--;
  44. }
  45. else i++;
  46. }
  47. n = s.size();
  48. f=0,e=0;
  49. for(int i=0;i<n;i++){
  50. if(s[i] == '(')
  51. f++;
  52. else
  53. e++;
  54. }
  55. if(f==n || e==n){
  56. cout << n*a << endl;
  57. return;
  58. }
  59. if(f==e){
  60. cout << min(n*a , f*b) << endl;
  61. return;
  62. }
  63. int mn = abs(f-e);
  64. int cnt = mn*a;
  65. cnt += min(f,e) * b;
  66. cnt = min(cnt,n*a);
  67. cout << cnt << endl;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement