Problem:


坑道数式

ある日廃坑を探検していたあなたは、坑道に長い数式 S が書かれているのを発見した。大きな数が好きなあなたは、チョークを取り出し、数式を計算した結果ができるだけ大きくなるように(または)を書き加えることにした。書き加えた後も数式になっていなければならないとすると、最大でいくつにできるか。

文字と文字の間は十分広く空いていて、(または)であればいくつでも書き加えることができる。最終的に数式になっていれば、最初のかっこの対応が崩れるように(または)を書いてもよい（Sample 2参照）。
また、ここでは以下のBNFで定義される<expr>を数式と呼ぶ。数式中の数は全て一桁である。

<expr>  ::= "(" <expr> ")"
         | <term> "+" <term>
         | <term> "-" <term>
<term>  ::= <digit> | <expr>
<digit> ::= "0" | "1" | "2" | "3" | "4"
          | "5" | "6" | "7" | "8" | "9"

Constraints

3 ≤ |S| ≤ 200

S は数式を表す。

Input Format

入力は以下の形式で標準入力から与えられる。

S

Output Format

答えを整数で出力せよ。

Sample Input 1

1-(2+3-4+5)

Sample Output 1

5

1-(2+3-(4+5))が最大となる。

Sample Input 2

1-(2+3+4)

Sample Output 2

0

(1-(2+3)+4)が最大となる。

Sample Input 3

1-(2+3)

Sample Output 3

-4

1-(2)+(3)はここでいう数式ではないことに注意。



Sample input:
1-(2+3-4+5)


Sample output:
5

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    fm = {}

    def sa(s):
        a = []
        for c in s:
            if '0' <= c <= '9':
                ci = int(c)
                if len(a) > 0 and isinstance(a[-1], int):
                    a[-1] = a[-1] * 10 + ci
                else:
                    a.append(ci)
            else:
                a.append(c)
        return a

    def f(s, sf):
        key = (s, sf)
        if key in fm:
            return fm[key]
        # print(s,sf)
        a = sa(s)
        l = len(a)
        r = None
        for i in range(2,l-2):
            if not isinstance(a[i], int):
                continue
            if a[i-1] == '(' or a[i+1] == ')':
                continue
            tl = f(''.join(map(str, a[:i+1])), sf)
            if tl is None:
                continue
            if a[i+1] == '+':
                tr = f(''.join(map(str, a[i+2:])), sf)
                if not tr is None:
                    tl += tr
                else:
                    tl = None
            else:
                tr = f(''.join(map(str, a[i+2:])), not sf)
                if not tr is None:
                    tl -= tr
                else:
                    tl = None
            if tl is None:
                continue
            if sf:
                if r is None or r < tl:
                    r = tl
            else:
                if r is None or r > tl:
                    r = tl

        kc = 0
        for c in a:
            if c == '(':
                kc += 1
            elif c == ')':
                kc -= 1
                if kc < 0:
                    kc = 0
        if kc > 0:
            a += [')'] * kc
        kc = 0
        for c in a[::-1]:
            if c == '(':
                kc -= 1
                if kc < 0:
                    kc = 0
            elif c == ')':
                kc += 1
        if kc > 0:
            a = ['('] * kc + a

        while '(' in a:
            # print('while (', a)
            i = len(a) - 1
            while '(' != a[i]:
                i -= 1
            j = a.index(')', i)
            if j-i < 2:
                break
            tr = a[i+1]
            for k in range(i+2,j,2):
                if a[k] == '+':
                    tr += a[k+1]
                else:
                    tr -= a[k+1]
            a[i:j+1] = [tr]

        if not '(' in a:
            # print('not (', a)
            tr = a[0]
            for i in range(1,len(a),2):
                if a[i] == '+':
                    tr += a[i+1]
                else:
                    tr -= a[i+1]
            if sf:
                if r is None or r < tr:
                    r = tr
            else:
                if r is None or r > tr:
                    r = tr

        fm[key] = r
        return r


    r = f(s, True)
    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    fm = {}

    def sa(s):
        a = []
        for c in s:
            if '0' <= c <= '9':
                ci = int(c)
                if len(a) > 0 and isinstance(a[-1], int):
                    a[-1] = a[-1] * 10 + ci
                else:
                    a.append(ci)
            else:
                a.append(c)
        return a

    def f(s, sf):
        key = (s, sf)
        if key in fm:
            return fm[key]
        # print(s,sf)
        a = sa(s)
        l = len(a)
        if l == 1:
            if isinstance(a[0], int):
                return a[0]
            return None
        r = None
        for i in range(0,l-2):
            if not isinstance(a[i], int):
                continue
            if a[i-1] == '(' or a[i+1] == ')':
                continue
            tl = f(''.join(map(str, a[:i+1])), sf)
            if tl is None:
                continue
            if a[i+1] == '+':
                tr = f(''.join(map(str, a[i+2:])), sf)
                if not tr is None:
                    tl += tr
                else:
                    tl = None
            else:
                tr = f(''.join(map(str, a[i+2:])), not sf)
                if not tr is None:
                    tl -= tr
                else:
                    tl = None
            if tl is None:
                continue
            if sf:
                if r is None or r < tl:
                    r = tl
            else:
                if r is None or r > tl:
                    r = tl

        kc = 0
        for c in a:
            if c == '(':
                kc += 1
            elif c == ')':
                kc -= 1
                if kc < 0:
                    kc = 0
        if kc > 0:
            a += [')'] * kc
        kc = 0
        for c in a[::-1]:
            if c == '(':
                kc -= 1
                if kc < 0:
                    kc = 0
            elif c == ')':
                kc += 1
        if kc > 0:
            a = ['('] * kc + a

        while '(' in a:
            # print('while (', a)
            i = len(a) - 1
            while '(' != a[i]:
                i -= 1
            j = a.index(')', i)
            if j-i < 2:
                break
            tr = a[i+1]
            for k in range(i+2,j,2):
                if a[k] == '+':
                    tr += a[k+1]
                else:
                    tr -= a[k+1]
            a[i:j+1] = [tr]

        if not '(' in a:
            # print('not (', a)
            tr = a[0]
            for i in range(1,len(a),2):
                if a[i] == '+':
                    tr += a[i+1]
                else:
                    tr -= a[i+1]
            if sf:
                if r is None or r < tr:
                    r = tr
            else:
                if r is None or r > tr:
                    r = tr

        fm[key] = r
        return r


    r = f(s, True)
    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    fm = {}

    def sa(s):
        a = []
        for c in s:
            if '0' <= c <= '9':
                ci = int(c)
                if len(a) > 0 and isinstance(a[-1], int):
                    a[-1] = a[-1] * 10 + ci
                else:
                    a.append(ci)
            else:
                a.append(c)
        return a

    def f(s, sf):
        key = (s, sf)
        if key in fm:
            return fm[key]
        # print(s,sf)
        if s[0] == '(' and s[-1] == ')':
            s = s[1:-1]
        a = sa(s)
        l = len(a)
        if l == 1:
            if isinstance(a[0], int):
                return a[0]
            return None
        r = None
        for i in range(0,l-2):
            if not isinstance(a[i], int):
                continue
            if a[i-1] == '(' or a[i+1] == ')':
                continue
            tl = f(''.join(map(str, a[:i+1])), sf)
            if tl is None:
                continue
            if a[i+1] == '+':
                tr = f(''.join(map(str, a[i+2:])), sf)
                if not tr is None:
                    tl += tr
                else:
                    tl = None
            else:
                tr = f(''.join(map(str, a[i+2:])), not sf)
                if not tr is None:
                    tl -= tr
                else:
                    tl = None
            if tl is None:
                continue
            if sf:
                if r is None or r < tl:
                    r = tl
            else:
                if r is None or r > tl:
                    r = tl

        kc = 0
        for c in a:
            if c == '(':
                kc += 1
            elif c == ')':
                kc -= 1
                if kc < 0:
                    kc = 0
        if kc > 0:
            a += [')'] * kc
        kc = 0
        for c in a[::-1]:
            if c == '(':
                kc -= 1
                if kc < 0:
                    kc = 0
            elif c == ')':
                kc += 1
        if kc > 0:
            a = ['('] * kc + a

        while '(' in a:
            # print('while (', a)
            i = len(a) - 1
            while '(' != a[i]:
                i -= 1
            j = a.index(')', i)
            if j-i < 2:
                break
            tr = a[i+1]
            for k in range(i+2,j,2):
                if a[k] == '+':
                    tr += a[k+1]
                else:
                    tr -= a[k+1]
            a[i:j+1] = [tr]

        if not '(' in a:
            # print('not (', a)
            tr = a[0]
            for i in range(1,len(a),2):
                if a[i] == '+':
                    tr += a[i+1]
                else:
                    tr -= a[i+1]
            if sf:
                if r is None or r < tr:
                    r = tr
            else:
                if r is None or r > tr:
                    r = tr

        fm[key] = r
        return r


    r = f(s, True)
    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    fm = {}

    a = []
    for c in s:
        if '0' <= c <= '9':
            ci = int(c)
            if len(a) > 0 and isinstance(a[-1], int):
                a[-1] = a[-1] * 10 + ci
            else:
                a.append(ci)
        else:
            a.append(c)

    def f(a):
        key = tuple(a)
        if key in fm:
            return fm[key]
        if len(a) == 2:
            fm[key] = [inf,-inf]
            return [inf,-inf]
        for i in range(len(a)):
            if a[i] != '(':
                if i > 0:
                    a = a[i:]
                break
        for i in range(len(a)-1,-1,-1):
            if a[i] != ')':
                a = a[:i+1]
                break
        if len(a) == 1:
            r = [a[0],a[0]]
            fm[key] = r
            return r

        ri = [inf]
        ra = [-inf]
        for i in range(1,len(a)-1):
            if not a[i] in ['+','-']:
                continue
            fl = f(a[:i])
            fr = f(a[i+1:])
            if a[i] == '+':
                ri.append(fl[0]+fr[0])
                ra.append(fl[1]+fr[1])
            else:
                ri.append(fl[0]-fr[1])
                ra.append(fl[1]-fr[0])

        r = [min(ri), max(ra)]
        fm[key] = r
        return r

    r = f(a)
    return r[1]


print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    fm = {}

    a = []
    for c in s:
        if '0' <= c <= '9':
            ci = int(c)
            if len(a) > 0 and isinstance(a[-1], int):
                a[-1] = a[-1] * 10 + ci
            else:
                a.append(ci)
        else:
            a.append(c)

    def f(a):
        key = tuple(a)
        if key in fm:
            return fm[key]
        if len(a) == 2:
            fm[key] = [inf,-inf]
            return [inf,-inf]
        for i in range(len(a)):
            if a[i] != '(':
                if i > 0:
                    a = a[i:]
                break
        for i in range(len(a)-1,-1,-1):
            if a[i] != ')':
                a = a[:i+1]
                break
        if len(a) == 1:
            r = [a[0],a[0]]
            fm[key] = r
            return r

        ri = [inf]
        ra = [-inf]
        l = len(a)
        for i in range(1,len(a)-1):
            if not a[i] in ['+','-'] or (i > 1 and a[i-2] == '(') or (i+2 < l and a[i+2] == ')'):
                continue
            fl = f(a[:i])
            fr = f(a[i+1:])
            if a[i] == '+':
                ri.append(fl[0]+fr[0])
                ra.append(fl[1]+fr[1])
            else:
                ri.append(fl[0]-fr[1])
                ra.append(fl[1]-fr[0])

        r = [min(ri), max(ra)]
        fm[key] = r
        return r

    r = f(a)
    # print(r)
    # for k in sorted(fm.keys(), key=lambda x: [len(str(x)), str(x)]):
    #     print('k,fm[k]', ''.join(map(str,k)),fm[k])
    return r[1]


print(main())