Submission #8853102

---

Source Code Expand

from copy import deepcopy
 
 
class Solver():
    def __init__(self, n, t):
        self.n = n
        self.t = t
 
    def depth_first_search(self,
                           niku_index: int,
                           yaki_index: int,
                           cumulative_times) -> int:
 
        cumulative_times[yaki_index] += self.t[niku_index]
        if niku_index == self.n - 1:
            return max(cumulative_times)
 
        return min(
            self.depth_first_search(niku_index + 1, 0, deepcopy(cumulative_times)),
            self.depth_first_search(niku_index + 1, 1, deepcopy(cumulative_times))
        )
 
    def solve(self) -> int:
        return min(
            self.depth_first_search(0, 0, [0, 0]),
            self.depth_first_search(0, 1, [0, 0])
        )
 
 
if __name__ == "__main__":
    n = int(input())
    t = []
    for _ in range(n):
        t.append(int(input()))
    s = Solver(n, t)
    print(s.solve())

Submission Info

Judge Result