2285.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2285 on 2006-09-10 at 19:55:15 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int N = 512;
const int INF = 1 << 30;

class Board {
public:
	int a, b;
	char bs;
	void set(int ca, int cb, char bst) { a = ca; b = cb; bs = bst; }
	int getScore(int k) const { return k ? a : b; }
	bool operator <(const Board& bx) const { return a+b > bx.a+bx.b; }
};

Board b[N];
int bn;

bool better(pii, pii);
bool better(int, int, int);
pii play(char);

int main()
{
	int as, bs, n;

	while(scanf("%d %d %d", &as, &bs, &n) != EOF) {
		for(int i = bn = 0; i < n; i++) {
			int ax, bx; char ast, bst;
			scanf("%d %d\n%c\n%c", &ax, &bx, &ast, &bst);
			if(ast == 'S') as += ax;
			else b[bn++].set(ax, bx, bst);
		}
		sort(b, b+bn);
		pii bss = play('S'), bgs = play('G');
		if(better(bgs, bss)) swap(bgs, bss);
		if(bss.first == -INF) bss = pii(0, 0);
		printf("%d %d\n", as+bss.first, bs+bss.second);
	}
	
	return 0;
}

bool better(pii s1, pii s2)
{
	if(s1.first-s1.second != s2.first-s2.second) return s1.first-s1.second > s2.first-s2.second;
	else return s1 > s2;
}
bool better(int i, int j, int p)
{
	if(b[i].a+b[i].b != b[j].a+b[j].b) return b[i].a+b[i].b > b[j].a+b[j].b;
	else return b[i].getScore(p) > b[j].getScore(p);
}
pii play(char s)
{
	bool use[N] = { false };
	int ax = 0, bx = 0, id = -1;
	for(int i = 0; i < bn; i++)
		if(s == b[i].bs) { id = i; break; }
	if(id == -1) return pii(-INF, INF);
	use[id] = true; ax = b[id].a;
	int rn = bn-1;
	for(int i = 0; i < bn; i++)
		if(b[i].bs == 'S' && !use[i]) { use[i] = true; rn--; bx += b[i].b; }
	for(int i = 0; i < rn; i++) {
		int k = -1;
		for(int j = 0; j < bn; j++)
			if(use[j]) continue;
			else if(k == -1 || better(j, k, i&1)) k = j;
		((i&1) ? ax : bx) += b[k].getScore(i&1);
		use[k] = true;
	}
	return pii(ax, bx);
}