I think my implementation for the second scenario (attacking only his attack cards) might be wrong or overlooking some cases.
Here’s the submission link: Submission #239834662 - Codeforces
Here’s my code:
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
#define ll long long
#define vll vector<long long>
#define f(i,s,e) for(long long int i=s;i<e;i++)
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, m;
cin >> n >> m;
vll mattack, mdefence;
f(i, 0, n) {
string type;
ll strength;
cin >> type >> strength;
if (type == "ATK")
mattack.push_back(strength);
else
mdefence.push_back(strength);
}
sort(mattack.begin(), mattack.end());
vll power;
f(i, 0, m) {
ll cur;
cin >> cur;
power.push_back(cur);
}
// Scenerio 1: I demolish monkey
ll ans1 = 0;
multiset<ll> tpower(power.begin(), power.end());
// Destroy the defence
for (ll strength : mdefence) {
auto card = tpower.upper_bound(strength);
if (card == tpower.end()) {
ans1 = -1;
break;
}
tpower.erase(card);
}
// Total damage output
for (ll strength : tpower)
ans1 += strength;
for (ll strength : mattack)
ans1 -= strength;
// Scenerio 2: Just attack his attack cards
ll t = (m > mattack.size()) ? m : mattack.size();
ll ans2 = 0;
if (t) {
sort(power.begin(), power.end(), greater<>());
ll curpower = 0, curattack = 0;
f(i, 0, t) {
if (power[i] < mattack[i])
break;
curpower += power[i];
curattack += mattack[i];
ans2 = max(ans2, curpower - curattack);
}
}
cout << max(ans1, ans2) << endl;
}