CodeForces 3D-Least Cost Bracket Sequence
1583 ワード
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <cctype>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <iomanip>
#include <set>
#include <vector>
#include <cstdio>
#include <stack>
#include <sstream>
#include <cstring>
#include <map>
using namespace std;
int main()
{
string str1;
cin>>str1;
int lenth=str1.size();
priority_queue<pair<int,int> > que;
long long cnt=0,sum=0;
pair<int,int> tmp;
bool flag=false;
for(int i=0;i<lenth;i++)
{
if(str1[i]=='(')
cnt++;
else if(str1[i]==')')
cnt--;
else
{
cnt--;
int tmp1,tmp2;
cin>>tmp1>>tmp2;
sum+=tmp2;
str1[i]=')';
que.push(make_pair(tmp2-tmp1,i));
}
if(cnt<0)
{
if(que.empty())
{
flag=true;
continue;
}
tmp=que.top();
sum-=tmp.first;
str1[tmp.second]='(';
cnt+=2;
que.pop();
}
}
//cout<<cnt<<endl;
if(cnt!=0||flag)
printf("-1
");
else
cout<<sum<<endl<<str1<<endl;
return 0;
}
すごい人に学べ!がんばって!