Problem:


Score : 100 points

Problem Statement

Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.

The vacation consists of N days.
For each i (1 \leq i \leq N), Taro will choose one of the following activities and do it on the i-th day:

A: Swim in the sea. Gain a_i points of happiness.

B: Catch bugs in the mountains. Gain b_i points of happiness.

C: Do homework at home. Gain c_i points of happiness.

As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.

Find the maximum possible total points of happiness that Taro gains.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq a_i, b_i, c_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

Output

Print the maximum possible total points of happiness that Taro gains.

Sample Input 1

3
10 40 70
20 50 80
30 60 90

Sample Output 1

210

If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.

Sample Input 2

1
100 10 1

Sample Output 2

100

Sample Input 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Sample Output 3

46

Taro should do activities in the order C, A, B, A, C, B, A.



Sample input:
3
10 40 70
20 50 80
30 60 90


Sample output:
210

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    actividad = []
    for i in range(n):
        puntos = list(map(int, input().split()))
        actividad.append(puntos)

    primer_puntos = [0] * 3

    for i in range(len(primer_puntos)):
        primer_puntos[i] = actividad[0][i]

    for i in range(1, n):
        siguiente = [0] * 3
        for j in range(3):
            for k in range(3):
                if j != k :
                    siguiente[j] = max(siguiente[j], primer_puntos[k] + actividad[i][j])
        primer_puntos = siguiente

    print(max(primer_puntos))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, factor = getInputs()

    points = []
    for i in range(n):
        points.append([0] * 3)

    # points[day][pile]
    for pile in range(3):
        points[0][pile] = factor[0][pile]

    for day in range(1, n):
        points[day][0] = max(points[day - 1][1], points[day - 1][2]) + factor[day][0]
        points[day][1] = max(points[day - 1][0], points[day - 1][2]) + factor[day][1]
        points[day][2] = max(points[day - 1][0], points[day - 1][1]) + factor[day][2]

    print(max(points[-1]))

def getInputs():
    n = int(input())

    factor = []
    for i in range(n):
        factor.append(tuple(map(lambda x: int(x), input().split())))

    return n, factor

main()

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
c = []
for i in range(n):
    a_,b_,c_ = map(int,input().split())
    a.append(a_)
    b.append(b_)
    c.append(c_)
dp = [[0]*3 for i in range(n+1)]
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for i in range(1,n):
    for j in range(3):
        if j == 0:
           dp[i][j] = max(a[i]+dp[i-1][1],a[i]+dp[i-1][2]) 
        elif j == 1:
           dp[i][j] = max(b[i]+dp[i-1][0],b[i]+dp[i-1][2]) 
        elif j == 2:
           dp[i][j] = max(c[i]+dp[i-1][1],c[i]+dp[i-1][0]) 
            
print(max(dp[n-1][j] for j in range(3)))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]

# dp
dp_a = [0 for _ in range(N)]
dp_b, dp_c = dp_a.copy(), dp_a.copy()
dp_a[0] = abc[0][0]
dp_b[0] = abc[0][1]
dp_c[0] = abc[0][2]

for i in range(N - 1):
    dp_a[i + 1] = max(dp_b[i], dp_c[i]) + abc[i + 1][0]
    dp_b[i + 1] = max(dp_a[i], dp_c[i]) + abc[i + 1][1]
    dp_c[i + 1] = max(dp_a[i], dp_b[i]) + abc[i + 1][2]
print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

Submission status: Accepted

Solution code:
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
a.insert(0, [0, 0, 0])
dp = [[0, 0, 0] for _ in range(N+1)]
for i in range(1, N + 1):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], a[i][j] + dp[i - 1][k])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

activies = []
for i in range(N):
    activies.append(list(map(int, input().split())))

n_activivies = len(activies[0])

dp = [[0 for _ in range(n_activivies)] for _ in range(N)]
for i in range(n_activivies):
    dp[0][i] = activies[0][i]

for day in range(1, N):
    for prev_activity in range(n_activivies):
        for cur_activity in range(n_activivies):
            if cur_activity != prev_activity:
                dp[day][cur_activity] = max(
                    dp[day][cur_activity], dp[day-1][prev_activity] + activies[day][cur_activity]
                )

print(max(dp[N-1]))

Submission status: Accepted

Solution code:
N=int(input())
l=[]
for n in range(N):
    l.append(list(map(int,input().strip().split())))

dp=[[0,0,0] for n in range(N)]
dp[0]=l[0]
for n in range(1,N):
    for i in range(3):
        for j in range(3):
            if i!=j:
                dp[n][i]=max(dp[n][i],dp[n-1][j]+l[n][i])
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n + 1)]

for i in range(n):
    for now in range(3):
        for prev in range(3):
            if now == prev:
                continue

            dp[i+1][now] = max(dp[i+1][now], dp[i][prev] + abc[i][now])

ans = max(dp[-1])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
list_=[]

a = [0]*n
b = [0]*n
c = [0]*n

for i in range(n):
  a[i],b[i],c[i] = map(int, input().split())

dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)

for i in range(1,n):
  dpa[i] = max(dpb[i-1]+a[i], dpc[i-1]+a[i])
  dpb[i] = max(dpa[i-1]+b[i], dpc[i-1]+b[i])
  dpc[i] = max(dpa[i-1]+c[i], dpb[i-1]+c[i])
  
print(max(dpa[-1], dpb[-1], dpc[-1]))

Submission status: Accepted

Solution code:
import sys
def main():
    N=int(sys.stdin.readline())
    a=[]
    for _ in [0]*N:a.append(list(map(int,sys.stdin.readline().split())))
    dp=[[0,0,0] for _ in [0]*N]
    dp[0]=a[0]
    for i in range(1,N):
        for j in range(3):dp[i][j]=max([dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]])+a[i][j]
    print(max(dp[N-1]))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
n=int(input())

dp=[0]*n
dp[0]=list(map(int,input().split()))

for i in range(1,n):
    dp[i]=list(map(int,input().split()))
    dp[i][0]+=max(dp[i-1][1],dp[i-1][2])
    dp[i][1]+=max(dp[i-1][0],dp[i-1][2])
    dp[i][2]+=max(dp[i-1][0],dp[i-1][1])

print(max(dp[n-1]))

Submission status: Accepted

Solution code:
N = int(input())
ABC = [None] * N
for i in range(N):
    ABC[i] = list(map(int, input().split()))

l = [[None] * 3 for _ in range(N)]
for i in range(N):
    l[i] = (ABC[i])

dp = [[0] * 3 for _ in range(N)]
dp[0] = ABC[0]

for i in range(1, N):
    dp_p = sorted(dp[i - 1])
    a = dp_p[-1]
    b = dp[i - 1].index(a)
    for j in range(3):
        if j == b:
            dp[i][j] = dp_p[-2] + l[i][j]
        else:
            dp[i][j] = a + l[i][j]
ans = max(dp[-1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N)]
dp= [[0]*3 for i in range(N)]

for i in range(N):
    if i == 0:
        dp[0][0] = ABC[0][0]
        dp[0][1] = ABC[0][1]
        dp[0][2] = ABC[0][2]
    else:
        dp[i][0] = max(ABC[i][0]+dp[i-1][1], ABC[i][0]+dp[i-1][2])
        dp[i][1] = max(ABC[i][1]+dp[i-1][0], ABC[i][1]+dp[i-1][2])
        dp[i][2] = max(ABC[i][2]+dp[i-1][0], ABC[i][2]+dp[i-1][1])

print(max(dp[N-1]))

Submission status: Accepted

Solution code:
n = int(input())
memo = []
memo1 = [0,0,0]
for i in range(n):
    s = input().split()
    s = [int(s[j]) for j in range(3)]
    if i==0:
        memo = s
    else:
        memo1[0] = max(memo[1],memo[2])+s[0]
        memo1[1] = max(memo[0],memo[2])+s[1]
        memo1[2] = max(memo[0],memo[1])+s[2]
        memo = [1*memo1[j] for j in range(3)]
print(max(memo))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    abc = [list(map(int, input().split())) for _ in range(n)]

    dp = [0]*(n+1)
    for x in range(n+1):
        dp[x] = [0, 0, 0]

    for i in range(1, n+1):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i][k] = max(dp[i][k], dp[i-1][j] + abc[i-1][k])

    ans = 0
    for i in range(3):
        ans = max(ans, dp[n][i])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    #N, K = map(int, input().split())
    N = int(input())

    dp = []

    for i in range(N):
        vals = list(map(int, input().split()))
        happy = {}
        for j in range(3):
            if dp:
                happy[j] = max([dp[i-1][k] + vals[j]
                                for k in range(3) if k != j])
            else:
                happy[j] = vals[j]
        dp.append(happy)

    print(max(dp[-1].values()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
b = [None]*n
c = [None]*n
for i in range(n):
    a[i],b[i],c[i] = map(int, input().split())
    
dpa = [0]*(n+1)
dpb = [0]*(n+1)
dpc = [0]*(n+1)

for i in range(1,n+1):
    aa,bb,cc = a[i-1],b[i-1],c[i-1]
    dpa[i] = max(dpb[i-1]+aa, dpc[i-1]+aa)
    dpb[i] = max(dpa[i-1]+bb, dpc[i-1]+bb)
    dpc[i] = max(dpa[i-1]+cc, dpb[i-1]+cc)
print(max(dpa[n], dpb[n], dpc[n]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]

dp = [[0, 0, 0]] * (N+1)

for i in range(1, N+1):
    tmp1 = max([dp[i-1][1]+abc[i-1][0], dp[i-1][2]+abc[i-1][0]])
    tmp2 = max([dp[i-1][0]+abc[i-1][1], dp[i-1][2]+abc[i-1][1]])
    tmp3 = max([dp[i-1][0]+abc[i-1][2], dp[i-1][1]+abc[i-1][2]])
    dp[i] = [tmp1, tmp2, tmp3]
    
print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
a = []*N
b = []*N
c = []*N
for _ in range(N):
    A, B, C = map(int, input().split())
    a.append(A)
    b.append(B)
    c.append(C)

dp = [[0,0,0] for _ in range(N)]
dp[0] = [a[0],b[0],c[0]]
for i in range(1, N):
    dp[i][0] = max(dp[i-1][1]+a[i], dp[i-1][2]+a[i])
    dp[i][1] = max(dp[i-1][0]+b[i], dp[i-1][2]+b[i])
    dp[i][2] = max(dp[i-1][0]+c[i], dp[i-1][1]+c[i])

print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0]*3 for _ in range(n)]
a, b, c = map(int, input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c
for i in range(n-1):
    a, b, c = map(int, input().split())
    dp[i+1][0] = max(dp[i][1]+a, dp[i][2]+a)
    dp[i+1][1] = max(dp[i][0]+b, dp[i][2]+b)
    dp[i+1][2] = max(dp[i][0]+c, dp[i][1]+c)


print(max(dp[n-1]))

Submission status: Accepted

Solution code:
n = int(input())

a = [0 for i in range(n)]
b = [0 for i in range(n)]
c = [0 for i in range(n)]

for i in range(n):
    a[i], b[i], c[i] = list(map(int, input().split()))

dp = []

for i in range(n):
    dp.append([0, 0, 0])


dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for i in range(1, n):
    dp[i][0] = max(dp[i-1][1] + a[i], dp[i-1][2] + a[i])
    dp[i][1] = max(dp[i-1][0] + b[i], dp[i-1][2] + b[i])
    dp[i][2] = max(dp[i-1][0] + c[i], dp[i-1][1] + c[i])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
lst=[[0,0,0]]
for i in range(a):
  x,y,z=mi()
  lst.append([max(lst[i][1],lst[i][2])+x,max(lst[i][0],lst[i][2])+y,max(lst[i][1],lst[i][0])+z])
print(max(lst[-1]))

Submission status: Accepted

Solution code:
#dp[x][i]=x日目に、場所iへ、行くときの幸福度の総和の最大値 連日iに行くことはできない縛りがある
#直前＝昨日にいった場所をjとすると、j!=iで表せる 
n=int(input())

dp=[[0 for i in range(3)]for j in range(n)]
happy=[]
for i in range(n):
    a,b,c=map(int,input().split())
    happy.append((a,b,c))
for i in range(3):
    dp[0][i]=happy[0][i]
for i in range(1,n):
    for t_place in range(3):
        for y_place in range(3):
            if t_place==y_place:
                continue
            dp[i][t_place]=max(dp[i][t_place],dp[i-1][y_place]+happy[i][t_place])#昨日来た場所と今日行く場所の幸福度の和
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
n=int(input())
abc = [list(map(int, input().split())) for i in range(n)]
#[[10,40,70],[20,50,80],[30,60,90]]
ABC=[[0,0,0]]
#A = [0]
#B = [0]
#C = [0]
for i in range(n):
  a = abc[i][0] + max(ABC[-1][1], ABC[-1][2])#10+max(0,0),20+max(40,70)=90,30+max(120,120)=150
  b = abc[i][1] + max(ABC[-1][0], ABC[-1][2])#40+max(0,0),50+max(10,70)=120,60+max(90,120)=180
  c = abc[i][2] + max(ABC[-1][0], ABC[-1][1])#70+mac(0,0),80+max(10,40)=120,90+max(90,120)=210
  ABC += [[a,b,c]]
  #A += [a]#0,10,90,150
  #B += [b]#0,40,120,180
  #C += [c]#0,70,120,210
print(max(ABC[-1]))

Submission status: Accepted

Solution code:
n=int(input())
abc = [list(map(int, input().split())) for i in range(n)]
#[[10,40,70],[20,50,80],[30,60,90]]
A = [0]
B = [0]
C = [0]
for i in range(n):
  a = abc[i][0] + max(B[-1], C[-1])#10+max(0,0),20+max(40,70)=90,30+max(120,120)=150
  b = abc[i][1] + max(A[-1], C[-1])#40+max(0,0),50+max(10,70)=120,60+max(90,120)=180
  c = abc[i][2] + max(A[-1], B[-1])#70+mac(0,0),80+max(10,40)=120,90+max(90,120)=210
  A += [a]#0,10,90,150
  B += [b]#0,40,120,180
  C += [c]#0,70,120,210
print(max(A[-1], B[-1], C[-1]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = [tuple(map(int, input().split())) for _ in range(n)]

    dp = [[0, 0, 0] for _ in range(n + 1)]

    for i in range(n):
        a, b, c = x[i]
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a)
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][2] + a)
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b)
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][2] + b)
        dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c)
        dp[i + 1][2] = max(dp[i + 1][2], dp[i][1] + c)

    res = max(dp[-1])

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a, b, c = [], [], []
# dp = [[None] * 3 for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]

for i in range(n):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for idx in range(1, n):
    # Select A(0)
    a1 = dp[idx - 1][1] + a[idx]
    a2 = dp[idx - 1][2] + a[idx]
    dp[idx][0] = max(a1, a2)

    # Select B(1)
    b1 = dp[idx - 1][0] + b[idx]
    b2 = dp[idx - 1][2] + b[idx]
    dp[idx][1] = max(b1, b2)

    # Select C(2)
    c1 = dp[idx - 1][0] + c[idx]
    c2 = dp[idx - 1][1] + c[idx]
    dp[idx][2] = max(c1, c2)

print(max(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a, b, c = [], [], []
# dp = [[None] * 3 for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]

for i in range(n):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

def solve(idx, ptn):
    if dp[idx][ptn] > 0:
        return dp[idx][ptn]

    # Select A(0)
    if ptn == 0:
        if idx == 0:
            return a[0]
        a1 = solve(idx - 1, 1) + a[idx]
        a2 = solve(idx - 1, 2) + a[idx]
        dp[idx][0] = max(a1, a2)
        return dp[idx][0]

    # Select B(1)
    if ptn == 1:
        if idx == 0:
            return b[0]
        b1 = solve(idx - 1, 0) + b[idx]
        b2 = solve(idx - 1, 2) + b[idx]
        dp[idx][1] = max(b1, b2)
        return dp[idx][1]

    # Select C(2)
    if ptn == 2:
        if idx == 0:
            return c[0]
        c1 = solve(idx - 1, 0) + c[idx]
        c2 = solve(idx - 1, 1) + c[idx]
        dp[idx][2] = max(c1, c2)
        return dp[idx][2]

ans1 = solve(n-1, 0)
ans2 = solve(n-1, 1)
ans3 = solve(n-1, 2)
print(max(ans1, ans2, ans3))

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
ABC = [LI() for _ in range(N)]


def main():
    dp = [[0] * 3 for _ in range(N + 1)]
    for i in range(1, N + 1):
        a, b, c = ABC[i - 1]
        dp[i][0] = a + max(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = b + max(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = c + max(dp[i - 1][0], dp[i - 1][1])
    ans = max(dp[-1])
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

n = int(input());
arr = [];
for i in range(n):
    tarr = get_array();
    arr.append(tarr);
dp = [[0,0,0] for i in range(n)];
dp[0][0]=arr[0][0];
dp[0][1]=arr[0][1];
dp[0][2]=arr[0][2];
for i in range(1,n):
    for j in range(3):
        dp[i][j]=arr[i][j]+max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]);
print(max(dp[n-1]));

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0]*N for _ in range(3)]

a, b, c = map(int, input().split())
dp[0][0] = a
dp[1][0] = b 
dp[2][0] = c

for i in range(N-1):
    a, b, c = map(int, input().split())
    dp[0][i+1] = max(dp[1][i], dp[2][i]) + a
    dp[1][i+1] = max(dp[0][i], dp[2][i]) + b
    dp[2][i+1] = max(dp[0][i], dp[1][i]) + c

print(max([dp[0][-1], dp[1][-1], dp[2][-1]]))

Submission status: Accepted

Solution code:
#Educational-DP C
n = int(input())
vac = []
for i in range(n):
    vac.append(tuple(map(int,input().split())))

dp1 = [vac[0][0]] + [0] * (n-1)
dp2 = [vac[0][1]] + [0] * (n-1)
dp3 = [vac[0][2]] + [0] * (n-1)

for i in range(1,n):
    dp1[i] = max((vac[i][0]+dp2[i-1]),(vac[i][0]+dp3[i-1]))
    dp2[i] = max((vac[i][1]+dp1[i-1]),(vac[i][1]+dp3[i-1]))
    dp3[i] = max((vac[i][2]+dp2[i-1]),(vac[i][2]+dp1[i-1]))
    
    
print(max(dp1[-1],dp2[-1],dp3[-1]))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int, read().split())
dp = [0, 0, 0]
for a, b, c in zip(m, m, m):
    dp = [max(dp[1], dp[2]) + a, max(dp[0], dp[2]) + b, max(dp[0], dp[1]) + c]

print(max(dp))

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0] * 3 for i in range(n)]


a = [list(map(int, input().split())) for i in range(n)]

for i in range(3):
    dp[0][i] = a[0][i]

for i in range(n - 1):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][j]= max(dp[i + 1][j], dp[i][k] + a[i + 1][j])
            else:
                continue
                
print(max(max(dp[n - 1][0], dp[n - 1][1]),dp[n - 1][2]))

Submission status: Accepted

Solution code:
n = int(input())
arr = [[int(i) for i in list(input().split())] for j in range(n)]
for i in range(1,n):
	arr[i][0] += max(arr[i-1][1], arr[i-1][2])
	arr[i][2] += max(arr[i-1][1], arr[i-1][0])
	arr[i][1] += max(arr[i-1][0], arr[i-1][2])
print(max(arr[n-1]))

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0] * 3 for _ in range(n+1)]
for i in range(1,n+1):
  dp[i][0]=max(dp[i-1][1],dp[i-1][2])+l[i-1][0]
  dp[i][1]=max(dp[i-1][0],dp[i-1][2])+l[i-1][1]
  dp[i][2]=max(dp[i-1][0],dp[i-1][1])+l[i-1][2]

print(max(dp[n][0],dp[n][1],dp[n][2]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N + 1)]
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0
for i in range(1, N + 1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][j] = max(dp[i][j], dp[i - 1][k] + abc[i - 1][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
H = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N+1)]
# 0: umi, 1: yama, 2: HW

for i in range(1, N+1):
  for place in range(3):
    for place_y in range(3):
      if (place == place_y): continue
      dp[i][place] = max(
        dp[i][place],
        dp[i-1][place_y] + H[i-1][place]
      )

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
hap = []
for i in range(n):
    l = [int(x) for x in input().split()]
    hap += [l]
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = hap[0]
for i in range(1,n):
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3])+hap[i][j]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
INF = 10**18

if __name__ == "__main__":
    n = int(input())
    h = []
    for i in range(n):
        a,b,c = map(int,input().split())
        h.append([a,b,c])
    dp = [[0]*3 for i in range(n)]
    for i in range(n):
        if i == 0:
            dp[i][0] = h[i][0]
            dp[i][1] = h[i][1]
            dp[i][2] = h[i][2]
        else:
            for j in range(3):
                dp[i][0] = max(dp[i-1][1] + h[i][0],dp[i-1][2] + h[i][0])
                dp[i][1] = max(dp[i-1][0] + h[i][1],dp[i-1][2] + h[i][1])
                dp[i][2] = max(dp[i-1][0] + h[i][2],dp[i-1][1] + h[i][2])
    print(max(dp[-1]))

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*3)

dp = [[0]*3 for _ in range(N)]
for i, (a, b, c) in enumerate(A):
    if i == 0:
        dp[i] = [a, b, c]
        continue

    da, db, dc = dp[i-1]
    dp[i][0] = max(dp[i][0], max(db, dc)+a)
    dp[i][1] = max(dp[i][1], max(dc, da)+b)
    dp[i][2] = max(dp[i][2], max(da, db)+c)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

abc = [list(map(int, input().split())) for _ in range(n)]

# dp[i][j]: i日にj(a,b,c)を選んだときの幸福度
dp = [[0 for _ in range(3)] for _ in range(n)]
# 初日はそれぞれの幸福度
for i in range(3):
    dp[0][i] = abc[0][i]

for i in range(1, n):
    # i日目にaをするならi-1日目はb or c
    dp[i][0] = max(dp[i-1][1], dp[i-1][2])+abc[i][0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2])+abc[i][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1])+abc[i][2]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		n = inp()
		val = []
		for i in range(n):
			a = inlt()
			val.append(a)
		dp = [[0 for i in range(n)] for j in range(3)]
		dp[0][0] = val[0][0]
		dp[1][0] = val[0][1]
		dp[2][0] = val[0][2]
		for i in range(1,n):
			for j in range(3):
				dp[j][i] = val[i][j] + max(dp[(j+1)%3][i-1],dp[(j+2)%3][i-1])
		print(max(dp[0][n-1] , dp[1][n-1]  , dp[2][n-1] ))
if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n = i()
h = [intl() for _ in range(n)]

dp = [[0]*3 for _ in range(n)]
for i in range(n):
    if i == 0:
        dp[i][0] = h[i][0]
        dp[i][1] = h[i][1]
        dp[i][2] = h[i][2]
    else:
        for j in range(3):
           dp[i][0] = max( dp[i-1][1] + h[i][0], dp[i-1][2] + h[i][0] )
           dp[i][1] = max( dp[i-1][0] + h[i][1], dp[i-1][2] + h[i][1] )
           dp[i][2] = max( dp[i-1][0] + h[i][2], dp[i-1][1] + h[i][2] )
print( max(dp[n-1]) )

Submission status: Accepted

Solution code:
N=int(input())
dp=[0]*3
flag=0
for _ in range(N):
    a=list(map(int,input().split()))
    if flag==0:
        dp[0]=a[0]
        dp[1]=a[1]
        dp[2]=a[2]
        flag=1
    else:
        a0=dp[0]
        a1=dp[1]
        a2=dp[2]
        dp[0]=max(a[0]+a1,a[0]+a2)
        dp[1]=max(a[1]+a0,a[1]+a2)
        dp[2]=max(a[2]+a0,a[2]+a1)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
mo=998244353
n=int(input())
dp=list(map(int,input().split()))#[0,0,0]
for i in range(1,n):
    a,b,c=list(map(int,input().split()))
    dp=[a+max(dp[1],dp[2]),b+max(dp[0],dp[2]),c+max(dp[0],dp[1])]
print(max(dp))

Submission status: Accepted

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n = I()
    a = [Intl() for _ in range(n)]
    dp = [[0,0,0] for _ in range(n+1)]
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j == k:pass
                else:
                    dp[i+1][k] = max(dp[i+1][k],dp[i][j] + a[i][k])
    print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())
lis=[[] for _ in range(n)]
for i in range(n):
  a,b,c=map(int,input().split())
  lis[i]=[a,b,c]  
dp=[[0]*(n+1) for _ in range(3)]
for i in range(1,n+1):
  dp[0][i]=max(dp[1][i-1]+lis[i-1][0],dp[2][i-1]+lis[i-1][0])
  dp[1][i]=max(dp[0][i-1]+lis[i-1][1],dp[2][i-1]+lis[i-1][1])  
  dp[2][i]=max(dp[0][i-1]+lis[i-1][2],dp[1][i-1]+lis[i-1][2])
d=dp[0][n]
for i in range(1,3):
  if dp[i][n]>d:
    d=dp[i][n]
print(d)

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*3
for i in range(n):
    val=[int(x) for x in input().split()]
    temp=[0]*3
    for p in range(3):
        for k in range(3):
            if p!=k:
                temp[k]=max(temp[k],dp[p]+val[k])
        #print(temp)
    dp=temp[:]

print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())
abc = [[int(j) for j in input().split()] for i in range(N)]
dp = [[0] * 3]
for i in range(N):
    dp += [[max([dp[-1][p] + abc[i][n] for p in range(3) if p != n]) for n in range(3)]]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [[int(j) for j in input().split()] for i in range(N)]
dp = [[0] * 3]
for day in range(N):
    dp += [[max([dp[-1][p] + abc[day][n] for p in range(3) if p != n]) for n in range(3)]]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

INF = 1 << 60
dp = [[INF] * n + [0] for _ in range(3)]

# 直前の行動と次の行動だけシミュレーションすればよい
for i in range(n):
    a, b, c = map(int, input().split())
    dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + a
    dp[1][i] = max(dp[2][i - 1], dp[0][i - 1]) + b
    dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + c

print(max(list(zip(*dp))[n - 1]))

Submission status: Accepted

Solution code:
INF = float('inf')
def f_dp(x, a, b, c):
    dp = [[0] * (x + 1) for i in range(3)]
    dp[0][0] = a[0]
    dp[1][0] = b[0]
    dp[2][0] = c[0]

    for i in range(1, x):
        dp[0][i] = max(dp[1][i -1] + a[i], dp[2][i -1] + a[i])
        dp[1][i] = max(dp[0][i -1] + b[i], dp[2][i -1] + b[i])
        dp[2][i] = max(dp[0][i -1] + c[i], dp[1][i -1] + c[i])

    return dp

if __name__ == "__main__":
    n = int(input())
    abc = [map(int, input().split()) for _ in range(n)]
    a, b, c = [list(i) for i in zip(*abc)]
    dp = f_dp(n, a, b, c)

    print(max(dp[0][n-1], dp[1][n-1], dp[2][n-1]))

Submission status: Accepted

Solution code:
n = int(input())
li = [list(map(int,input().split())) for i in range(n)]
dp = [[0 for i in range(3)] for j in range(n+1)]

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k: #同じことを2日連続はできない
                continue
            dp[i+1][k] = max(dp[i+1][k], li[i][k] + dp[i][j])

print(max(dp[n]))

Submission status: Accepted

Solution code:
N = int(input())
abclist = [[0,0,0]]
for _ in range(N):
    a,b,c = map(int,input().split())
    abclist.append([a,b,c])
dp = [[-1,-1,-1] for _ in range(N+1)]
dp[0] = [0,0,0]
for i in range(1,N+1):
    for abc in [0,1,2]:
        if abc == 0: #a
            dp[i][abc] = max(dp[i-1][1]+abclist[i][0],dp[i-1][2]+abclist[i][0])
        elif abc == 1: #b
            dp[i][abc] = max(dp[i-1][0]+abclist[i][1],dp[i-1][2]+abclist[i][1])
        else:
            dp[i][abc] = max(dp[i-1][0]+abclist[i][2],dp[i-1][1]+abclist[i][2])
print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = list(map(int,input().split()))
dp = [[0 for j in range(3)] for i in range(n)]
dp[0] = a[0][:]
for i in range(1,n):
    dp[i][0] = max(dp[i-1][1]+a[i][0],dp[i-1][2]+a[i][0])
    dp[i][1] = max(dp[i-1][2]+a[i][1],dp[i-1][0]+a[i][1])
    dp[i][2] = max(dp[i-1][0]+a[i][2],dp[i-1][1]+a[i][2])
print(max(dp[-1][:]))

Submission status: Accepted

Solution code:
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(3)] for i in range(100010)]


DP= [[0 for j in range(3)] for i in range(100010)]

N=int(input())

for i in range(N):
    L=list(map(int,input().split()))
    for j in range(len(L)):
        S[i][j]=L[j]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k:
                pass
            else:
                if DP[i+1][k]<DP[i][j]+S[i][k]:
                    DP[i+1][k]=DP[i][j]+S[i][k]

ans=0
for j in range(3):
    if ans<DP[N][j]:
        ans=DP[N][j]
print(ans)