Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5.  
  6. ll ans, n, m;
  7. vector <ll> att, def, my;
  8.  
  9. ll with_def(){
  10. multiset <ll> S;
  11. for (auto e : my)
  12. S.insert(e);
  13.  
  14. my.clear();
  15. for (auto e : def){
  16. auto it = S.upper_bound(e);
  17. if (it == S.end()) return 0LL;
  18. S.erase(it);
  19. }
  20.  
  21. for (auto e : S)
  22. my.push_back(e);
  23.  
  24. sort(my.begin(), my.end());
  25. ll res = 0;
  26.  
  27.  
  28.  
  29. int poc = 0;
  30. for (auto e : my){
  31. if (poc == att.size()){
  32. res += e;
  33. continue;
  34. }
  35. if (e < att[poc])
  36. return 0LL;
  37. res += e - att[poc];
  38. poc ++;
  39. }
  40. return res;
  41. }
  42.  
  43.  
  44. ll try_attack(int cnt){
  45. ll res = 0;
  46. if (cnt > my.size()) return 0LL;
  47.  
  48. vector <ll> my_cards;
  49. vector <ll> to_attack;
  50.  
  51. for (int i = 0; i < cnt; i ++)
  52. my_cards.push_back(my[i]);
  53.  
  54. for (int i = att.size() - 1; to_attack.size() < cnt; i --)
  55. to_attack.push_back(att[i]);
  56.  
  57. sort(to_attack.begin(), to_attack.end());
  58. sort(my_cards.begin(), my_cards.end());
  59.  
  60. for (int i = 0; i < my_cards.size(); i ++){
  61. if (my_cards[i] < to_attack[i]) return 0LL;
  62. res += my_cards[i] - to_attack[i];
  63. }
  64. return res;
  65. }
  66.  
  67. int main(){
  68. cin >> n >> m;
  69. for (int i = 0; i < n; i ++){
  70. string s;
  71. int x;
  72. cin >> s >> x;
  73. if (s[0] == 'A')
  74. att.push_back(x);
  75. else
  76. def.push_back(x);
  77. }
  78. for (int i = 0; i < m; i ++){
  79. int x; cin >> x;
  80. my.push_back(x);
  81. }
  82. sort(my.begin(), my.end());
  83. sort(att.begin(), att.end());
  84. sort(def.begin(), def.end());
  85.  
  86. reverse(my.begin(), my.end());
  87. reverse(att.begin(), att.end());
  88. reverse(def.begin(), def.end());
  89.  
  90. for (int i = 1; i < att.size(); i ++)
  91. ans = max(ans, try_attack(i));
  92. cout << max(ans, with_def());
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement