結果

問題 No.3147 Parentheses Modification and Rotation (RM Ver.)
コンテスト
ユーザー tassei903
提出日時 2025-05-16 22:27:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 206 ms / 2,000 ms
コード長 1,572 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 147,712 KB
最終ジャッジ日時 2025-05-16 22:27:51
合計ジャッジ時間 5,149 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().strip()
ni = lambda : int(input())
na = lambda : list(map(int, input().split()))
yes = lambda : print("yes"); Yes = lambda : print("Yes"); YES = lambda : print("YES")
no = lambda : print("no"); No = lambda : print("No"); NO = lambda : print("NO")



class SparseTable():
    '''
    更新がないかつ冪等性が成り立つ場合
    '''
    def __init__(self, arr: list, op: callable=min) -> None:
        n = len(arr)
        h = n.bit_length()
        self.table = [[0] * n for _ in range(h)]
        self.table[0] = arr[::]
        for k in range(1, h):
            t, p = self.table[k], self.table[k - 1]
            l = 1 << (k - 1)
            for i in range(n - l * 2 + 1): t[i] = op(p[i], p[i + l])
        self.op = op

    def query(self, l: int, r: int) -> int:
        k = (r - l).bit_length() - 1
        return self.op(self.table[k][l], self.table[k][r - (1 << k)])

def solve(s):
    n = len(s)
    s = [0] + s + s
    for i in range(n*2):
        s[i+1] += s[i]
    sp = SparseTable(s)
    ans = []
    for i in range(n+1):
        ans.append(s[i] - sp.query(i, i + n + 1))
    return ans
n = ni()

s = [[-1, 1][x=="("] for x in input()]
if n % 2 == 1:
    print(-1)
    exit()
r, m = na()

# 置き換えての最初コストは左から見たpresumのmin+右から見たpresumのmin

A = solve(s)
B = solve([-x for x in s[::-1]])
C = [(A[i] + 1)//2 + (B[-1-i] + 1)//2 for i in range(n+1)]

# print(A)
# print(B)
ans = 10 ** 18

for i in range(n):
    ans = min(ans, C[-1-i] * m + i * r)

print(ans)
0