Codeforces 3D. Least Cost Bracket Sequence http://codeforces.com/problemset/problem/3/D 优先队列

CF3D.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

priority_queue<pair<long long, long long> > q;
string str;
long long tmp = 0, ans = 0, x, y;

int main() {
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			tmp++;
		} else if (str[i] == ')') {
			tmp--;
		} else {
			cin >> x >> y;
			str[i] = ')';
			ans += y;
			tmp--;
			q.push(make_pair(y-x, i));
		}
		if (tmp < 0) {
			if (q.empty()) break;
			pair<long long, long long> tem = q.top();
			q.pop();
			tmp += 2;
			ans -= tem.first;
			str[tem.second] = '(';
		}
	}
	if (tmp != 0)
		puts("-1");
	else
		cout << ans <<endl << str << endl;
	return 0;
}