[training day4] card game [greed]

Ideas ：

We found that , If you want to play defense cards , It must be all knocked out
So two strategies , A defense card , A non fight
Among them, playing cards that are a little bigger than defense cards is definitely the best
Then subtract the attack cards from the sum

$code$

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long

using namespace std;

const ll MAXN = 1e6 + 10;

ll n, m;
ll a[MAXN], b[MAXN], c[MAXN];

bool v[MAXN];

ll D() {
    
	ll i = m, j = 1, ans = 0;
	while(b[j] <= a[i] && i >= 1 && j <= b[0]) {
    
		ans += a[i] - b[j];
		i --, j ++;
	}
	return ans;
}

ll F() {
    
	ll j = 1;
	for(ll i = 1; i <= c[0]; i ++) {
    
		while(a[j] <= c[i] && j <= m) j ++;
		if(j > m) return 0;
		v[j] = 1;
		j ++;
	}
	j = 1;
	for(ll i = 1; i <= b[0]; i ++) {
    
		while(((a[j] < b[i]) || (v[j] == 1) ) && j <= m) j ++;
		if(j > m) return 0;
		j ++;
	}
	ll ans=0;
	for(ll i = 1; i <= m; i ++) ans += v[i] ? 0 : a[i];
	for(ll i = 1; i <= b[0]; i ++) ans -= b[i];
	return ans;
}

int main() {
    
	scanf("%lld%lld", &n, &m);
	string s;
	for(ll i = 1; i <= n; i ++) {
    
		cin>>s;
		if(s == "ATK") b[0] ++, scanf("%lld", &b[b[0]]);
		else c[0] ++, scanf("%lld", &c[c[0]]);
	}
	for(ll i = 1; i <= m; i ++) scanf("%lld", &a[i]);
	sort(a + 1, a + 1 + m);
	sort(b + 1, b + 1 + b[0]);
	sort(c + 1, c + 1 + c[0]);
	printf("%lld", max(D(), F()));
	return 0;
}