3 D Least Cost Bracket Sequence

問題

開き括弧、閉じ括弧、および?からなる文字列が与えられる。
この文字列の?を、開き括弧に変えるコスト、閉じ括弧に変えるコストが?ごとに与えられる。

このとき、括弧の対応が正しくなる式で、コストが最も小さいものおよびそのときのコストを出力せよ。

制約条件

n≦4*10^4

Editorial見た。

方針

• (が出てきたら深さを+1
• )が出てきたら深さを-1

するとする。
括弧の対応づけが正しいとは、各位置における括弧の深さが0以上で、かつ文字列終了時に深さが0であることである。

priority_queueを使う。
?が出てきたら、とりあえずそこは)が出てきたものとしておき、
priority_queueに、位置およびコストa[i]-b[i]を登録しておく。

深さが負になってしまったら、最もコストが安い?を(に変える。
priority queueが空だったら、どう?に括弧を割り当てても正しい対応が作れない。

ソースコード

string in;
int n,a[50000],b[50000],m;
int pos[50000],choose[50000];
void run()
{
	cin>>in;
	n=in.size();
	rep(i,n)if(in[i]=='?'){
		cin>>a[m]>>b[m];
		pos[m++]=i;
	}
	int depth=0,k=0; ll ans=0;
	priority_queue<pi> q;
	rep(i,n){
		if(in[i]=='(')depth++;
		else if(in[i]==')')depth--;
		else{
			q.push(mp(b[k]-a[k],i));
			ans+=b[k++];
			depth--;
		}
		if(depth<0){
			if(q.empty()){
				cout<<-1<<endl; return;
			}
			choose[q.top().second]=1;
			ans-=q.top().first; q.pop(); depth+=2;
		}
	}
/*
	for(;depth<0;depth+=2){
		if(q.empty()){
			cout<<-1<<endl; return;
		}
		choose[q.top().second]=1;
		ans-=q.top().first; q.pop();
	}
*/
	if(depth!=0){
		cout<<-1<<endl; return;
	}
	cout<<ans<<endl;
	rep(i,n)if(in[i]=='?')putchar(choose[i]?'(':')');
	else putchar(in[i]);
	puts("");
}