3 D. Least Cost Bracket Sequence

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef __int64 LL;
const LL INF = 1e9+7;
const LL MOD = 1e9+7;
const LL maxn = 50005;
char str[maxn];
LL n;
struct node
{
    int a, b, c;
    int Index;
    bool friend operator < (node B,node A)
    {
        return A.c < B.c;
    }
} P[maxn];

LL solve()
{
    LL k = 0, ans = 0, cnt = 0;
    priority_queue<node> Q;
    node Pn;
    for(int i=0; str[i]; i++)
    {
        if(str[i] == ‘?‘)
        {
            Q.push(P[k]);
            ans += P[k].b;
            str[i] = ‘)‘;
            k ++;
            cnt --;
        }
        else if(str[i] == ‘(‘)
            cnt ++;
        else
            cnt --;

        if(cnt < 0)
        {
            while(Q.size() && cnt < 0)
            {
                Pn =  Q.top();
                Q.pop();
                cnt += 2;
                ans = ans - Pn.b + Pn.a;
                str[Pn.Index] = ‘(‘;
            }
        }
        if(cnt < 0)
            return -1;
    }
    if(cnt > 0)
        return -1;
    return ans;
}


int main()
{
    scanf("%s", str);

    for(int i=0; str[i]; i++)
    {
        if(str[i] == ‘?‘)
        {
            scanf("%d %d", &P[n].a, &P[n].b);
            P[n].c = P[n].a - P[n].b;
            P[n ++].Index = i;
        }
    }
    LL ans = solve();

    printf("%I64d\n", ans);

    if(ans != -1)
        puts(str);

    return 0;
}