B - Parenthesis Arrangement
Source: atcoder
Difficulty: 400

Problem Statement
You are given a string
S
of length
2N
consisting of the characters
(
and
)
. Let
S_i
denote the
i
-th character from the left of
S
.
You can perform the following two types of operations zero or more times in any order:
Choose a pair of integers
(i,j)
such that
1\leq i < j \leq 2N
. Swap
S_i
and
S_j
. The cost of this operation is
A
.
Choose an integer
i
such that
1\leq i \leq 2N
. Replace
S_i
with
(
or
)
. The cost of this operation is
B
.
Your goal is to make
S
a correct parenthesis sequence. Find the minimum total cost required to achieve this goal. It can be proved that the goal can always be achieved with a finite number of operations.
What is a correct parenthesis sequence?
A correct parenthesis sequence is a string that satisfies any of the following conditions:
It is an empty string.
It is formed by concatenating
(
,
A
,
)
in this order where
A
is a correct parenthesis sequence.
It is formed by concatenating
A
and
B
in this order where
A
and
B
are correct parenthesis sequences.
Constraints
All input values are integers.
1 \leq N \leq 5\times 10^5
1\leq A,B\leq 10^9
S
is a string of length
2N
consisting of the characters
(
and
)
.
Input
The Input is given from Standard Input in the following format:
N
A
B
S
Output
Print the answer in a single line.
Sample Input 1
3 3 2
)))(()
Sample Output 1
5
Here is one way to operate:
Swap
S_3
and
S_4
.
S
becomes
))()()
. The cost is
3
.
Replace
S_1
with
(
.
S
becomes
()()()
, which is a correct parentheses sequence. The cost is
2
.
In this case, we have made
S
a correct bracket sequence for a total cost of
5
. There is no way to make
S
a correct bracket sequence for less than
5
.
Sample Input 2
1 175 1000000000
()
Sample Output 2
0
The given
S
is already a correct bracket sequence, so no operation is needed.
Sample Input 3
7 2622 26092458
))()((((()()((
Sample Output 3
52187538

C++ solution:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

void solve() {
	int n, a, b; cin >> n >> a >> b;
	
	string s; cin >> s;
	
	int op = 0, cl = 0;
	
	for(int i = 0; i < 2 * n; i++) {
		if(s[i] == '(') {
			op++;
		} else {
			if(op == 0) cl++;
			else op--;
		}
	}
	
	if(op < cl) swap(op, cl);
	
	op -= cl;
	
	op >>= 1;
	cl = (cl + 1) / 2;
	
	cout << min(a, 2 * b) * cl + op * b << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	_, A, B := readThreeNums(reader)
	s := readString(reader)

	res := solve(s, A, B)

	fmt.Println(res)
}

func readString(r *bufio.Reader) string {
	s, _ := r.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func solve(s string, A int, B int) int {
	n := len(s)
	// 不大对
	// 不得要领
	// 如果靠左有一个左括号，显然暂时不能替换和交换它
	// 把左右变成+1/-1, 那么是不是可以变成前缀和的形式
	// 假设交换 i, j, 那么对于j后面的前缀和来说，不会有影响
	// 如果替换i, 那么就会赢到i后面所有的数
	// 目的是使得，所有的前缀和>= 0, 且最后的前缀和 = 0
	// 可以使用两个replace 代替一个 swap
	A = min(A, 2*B)

	var level int
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			level++
		} else {
			level--
		}
	}
	// 如果level不等于0， 这些只能通过swap替换掉
	// 如果 level > 0, 那么必须替换左括号为右括号
	var res int

	buf := []byte(s)

	if level > 0 {
		// 左括号太多了，从后面往前replace
		for i := n - 1; level > 0; i-- {
			if buf[i] == '(' {
				level -= 2
				res += B
				buf[i] = ')'
			}
		}
	}
	if level < 0 {
		// 右括号太多了，从前面replace
		for i := 0; level < 0; i++ {
			if buf[i] == ')' {
				level += 2
				res += B
				buf[i] = '('
			}
		}
	}

	// level == 0
	// 然后就是用左括号和右括号交换
	var arr []int

	for i := 0; i < n; i++ {
		if buf[i] == '(' {
			arr = append(arr, i)
		}
	}
	// 肯定是各占一半的
	j := len(arr)

	for i := 0; i < n; i++ {
		if buf[i] == '(' {
			level++
		} else {
			level--
		}
		if level < 0 {
			buf[i], buf[arr[j-1]] = buf[arr[j-1]], buf[i]
			j--
			res += A
			level = 1
		}
	}

	return res
}


func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

public class Main {
  private static long solve(int n, long a, long b, char[] s) {
    int balance = 0;
    int minBalance = 0;
    for (char c : s) {
      if (c == '(') {
        balance++;
      } else {
        balance--;
      }
      minBalance = Math.min(minBalance, balance);
    }
    long cost = Math.abs(balance / 2) * b;
    if (balance < 0) {
      minBalance -= balance;
    }
    if (minBalance < 0) {
      cost += ((Math.abs(minBalance) + 1) / 2) * Math.min(2 * b, a);
    }
    return cost;
  }

  private static void execute(ContestReader reader, ContestWriter out) {
    int n = reader.nextInt();
    long a = reader.nextLong();
    long b = reader.nextLong();
    char[] s = reader.nextCharArray();
    out.println(solve(n, a, b, s));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printYN(boolean b) {
    println(b ? "Yes" : "No");
  }

  public void printYNList(List<Boolean> bList) {
    for (boolean b : bList) {
      printYN(b);
    }
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}

class ContestReader {
  private static final int BUFFER_SIZE = 1024;
  
  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;
  
  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }
  
  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }
    
    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }
  
  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }
  
  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }
  
  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }
  
  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public char nextChar() {
    return next().charAt(0);
  }
  
  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    int n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    long n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }
  
  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}

class Pair<T, U> {
  T first;
  U second;

  Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }
}

class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }
 
  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}

JavaScript solution:
const BigMath = {
    abs(x) {
      if (x < 0n) {
        return -1n * x;
      }
      return x;
    },
    min(base, ...values) {
      for (const value of values) {
        if (value < base) {
          base = value;
        }
      }
      return base;
    },
    max(base, ...values) {
      for (const value of values) {
        if (value > base) {
          base = value;
        }
      }
      return base;
    },
    pow(base, ex) {
      return base ** ex;
    },
    sign(x) {
      if (x === 0n) {
        return 0n;
      }
      return x < 0n ? -1n : 1n;
    },
  };
function Main(input)
{
    let [n, a, b] = input[0].split(" ").map(v => BigInt(v));
    n = parseInt(n);

    let s = input[1];

    let t = new Array(2 * n).fill(false);
    let q = [];
    let idx = 0;

    let d = 0n;
    let dc = 0n;
    let ans = 0n;
    for (let i = 0; i < n * 2; i++)
    {
        if (s[i] == "(")
        {
            q.push(i);
        }
        else
        {
            if (idx < q.length)
            {
                let i2 = q[idx++];
                t[i] = true;
                t[i2] = true;
            }
        }
    }
    for (let i = 0; i < n * 2; i++)
    {
        if (t[i]) continue;
        if (s[i] == "(")
        {
            d++;
        }
        else
        {
            d--;
            if (d < 0n)
            {
                dc++;
            }
        }
    }

    let cc = dc + BigMath.min(0n, d);
    ans += (cc + 1n) / 2n * BigMath.min(a, b * 2n);

    ans += BigMath.abs(d) / 2n * b;


    return `${ans}`;
}

let isSingle = true;
let data = `1 175 1000000000
()
`;
if (process.env.ATCODER == 1)
{
    data = require("fs").readFileSync("/dev/stdin", "utf8");
}
if (isSingle)
{
    console.log(Main(data.split("\n")));
}
else
{
    Main(data.split("\n"));
}

Python solution:
n,a,b=map(int,input().split())
A=[1 if s=='(' else -1 for s in input()]
x=A.count(1)
ans=0
if x>2*n-x:
  d=x-(2*n-x)
  for i in range(2*n-1,-1,-1):
    if A[i]==1:
      A[i]==-1
      d-=2
      ans+=b
      if d==0:
        break
elif x<2*n-x:
  d=2*n-x-x
  for i in range(2*n):
    if A[i]==-1:
      A[i]=1
      d-=2
      ans+=b
      if d==0:
        break
      
mn=float('inf')
cum=0
for x in A:
  cum+=x
  mn=min(mn,cum)
if mn<0:
  ans+=(abs(mn)+1)//2*min(a,2*b)
print(ans)

Ruby solution:
N,Sw,Tn = gets.split.map(&:to_i).then{|n,s,t| [n,[s,t+t].min,t] }
S = gets.chomp.bytes
l = r = 0
S.each{|c|
	case c
	when 0x28 # (
		l += 1
	when 0x29 # )
		if 0<l
			l -= 1
		else
			r += 1
		end
	end
}
s = ([l,r].min+1)/2
t = (([l,r].max-s*2)+1)/2
warn [l,r,s,t].inspect
p s*Sw+t*Tn