解法1：DP
考え方
dp[i][j] = i品目を食べて状態がj(0:お腹を壊していない/1:壊している)のときの食べた料理の美味しさの総和の最大値回答例
N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] dp = [[0]*2 for _ in range(N+1)] dp[0][1] = -1<<60 for i in range(N): x, y = XY[i] if x == 0: dp[i+1][0] = max(dp[i][0], dp[i][0] + y, dp[i][1] + y) dp[i+1][1] = dp[i][1] if x == 1: dp[i+1][0] = dp[i][0] dp[i+1][1] = max(dp[i][0] + y, dp[i][1]) print(max(dp[-1]))
