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:
"""
    Satwik_Tiwari ;) .
    24th july , 2020  - Friday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))

def solve():
    n = int(inp())
    temp = [0]
    for i in range(n):
        a,b,c = sep()
        temp.append([a,b,c])
    dp = [[0,0,0] for i in range(n+1)]
    dp[1][0] = temp[1][0]
    dp[1][1] = temp[1][1]
    dp[1][2] = temp[1][2]

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

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


testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  dp = [[float('inf')]*3 for _ in range(N)]
  dp[0] = list(map(int, input().split()))
  for i in range(1,N):
    a, b, c = map(int, input().split())
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a
    dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1])+c
  ans = max(dp[-1])
  return ans
print(solve())

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

a[0], b[0], c[0] = l[0][0], l[0][1], l[0][2]

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

print(max(a[-1],b[-1],c[-1]))

Submission status: Accepted

Solution code:
#import
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

a = []

# dp[i][0]:Aを選んだ  dp[i][1]:Bを選んだ  dp[i][2]:Cを選んだ 

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

for _ in range(N):
    aa = list(map(int, input().split()))
    a.append(aa)

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]+a[i-1][k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import math
N = int(input())
point_table = []
for _ in range(N):
  a,b,c = map(int, input().split())
  point_table.append([a, b, c])

dp_list = [[0] * 3 for _ in range(N)]
dp_list[0] = point_table[0].copy()

for i in range(N - 1):
  for j in range(3):
    for k in range(3):
      if j != k:
        cost = dp_list[i][j] + point_table[i + 1][k]
        if cost > dp_list[i + 1][k]:
          dp_list[i + 1][k] = cost

print(max(dp_list[-1]))

Submission status: Accepted

Solution code:
n = int(input())

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

days = [0]*n
for i in range(n):
    days[i] = list(map(int, input().split()))

a[0], b[0], c[0] = days[0][0], days[0][1], days[0][2]

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

print(max(a[-1], b[-1], c[-1]))

Submission status: Accepted

Solution code:
x=int(input())
days=[]
for i in range(x):
    days.append(list(map(int,input().split())))
#print(days)
dp=[0]*3
dp=days[0]
for cur in range(1,x):
    m=[0]*3
    for i in range(3):
        for j in range(3):
            if i!=j:
                m[i]=max(m[i],days[cur][i]+dp[j])
    dp=m
print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())

a,b,c = list(map(int, input().split()))
ai, bi, ci = 0,1,2

dp = [[0]*3 for _ in range(N)]
dp[0][ai] = a
dp[0][bi] = b
dp[0][ci] = c

for day in range(1, N):
    a,b,c = list(map(int, input().split()))
    dp[day][ai] += max(dp[day-1][bi], dp[day-1][ci]) + a
    dp[day][bi] += max(dp[day-1][ci], dp[day-1][ai]) + b
    dp[day][ci] += max(dp[day-1][ai], dp[day-1][bi]) + c

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
a,b,c = [],[],[]
for _ in range(n):
    A,B,C = map(int,stdin.readline().split())
    a.append(A)
    b.append(B)
    c.append(C)
dpa,dpb,dpc = [a[0]],[b[0]],[c[0]]
for i in range(1,n):
    dpa.append(a[i]+max(dpb[i-1],dpc[i-1]))
    dpb.append(b[i]+max(dpa[i-1],dpc[i-1]))
    dpc.append(c[i]+max(dpb[i-1],dpa[i-1]))
print(max(dpa[-1],dpb[-1],dpc[-1]))

Submission status: Accepted

Solution code:
from itertools import*
(n,), *D = [list(map(int, o.split())) for o in open(0)]
dp = [[0]*3 for _ in [None]*-~n]
for i in range(n):
  for j, k in permutations(range(3), 2):
    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + D[i][k])
print(max(dp[n]))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    dp = [[0] * 3 for _ in range(N + 1)]

    for i in range(1, N + 1):
        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]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from operator import itemgetter


def input():
    return sys.stdin.readline().rstrip()


def main():
    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 _ in range(N + 1)]
    for i in range(1, N + 1):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + A[i - 1]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + B[i - 1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + C[i - 1]
    print(max(dp[N]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = [na() for _ in range(n)]

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

    for i in range(n):
        for j in range(3):
            for k in range(1, 3):
                idx = (j + k) % 3
                dp[i + 1][idx] = max(dp[i + 1][idx], dp[i][j] + a[i][idx])

    print(max(dp[n]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
L = []
A,B,C = [],[],[]
for _ in range(n):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    L.append([a,b,c])
if n ==1: print(max(L[0]));exit()

for i in range(1,n):
    A[i],B[i],C[i] = A[i]+max(B[i-1],C[i-1]),B[i]+max(A[i-1],C[i-1]),C[i] + max(A[i-1],B[i-1])

print(max(A[-1],B[-1],C[-1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

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

D[0] = A[0]
for i in range(1, n):
    for j in range(3):
        D[i][j] = max(D[i-1][(j+1)%3], D[i-1][(j+2)%3]) + A[i][j]
print(max(D[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

dpa, dpb, dpc = [0]*(n+1), [0]*(n+1), [0]*(n+1)
dpa[0] = dpb[0] = dpc[0] = 0

for i in range(n):
    dpa[i + 1] = max(dpb[i] + p[i][0], dpc[i] + p[i][0])
    dpb[i + 1] = max(dpc[i] + p[i][1], dpa[i] + p[i][1])
    dpc[i + 1] = max(dpa[i] + p[i][2], dpb[i] + p[i][2])

print(max(dpa[n], dpb[n], dpc[n]))

Submission status: Accepted

Solution code:
n=int(input())
dp=[]
for i in range(n):
  l=list(map(int,input().split()))
  dp.append(l)
for i in range(1,n):
  for j in range(3):
  	dp[i][(j%3)]+=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())
H = [[0,0,0] for i in range(N)]
H[0] = list(map(int, input().split()))
for i in range(1, N):
    abc = list(map(int, input().split()))
    for j in range(3):
        H[i][j] = max(H[i-1][j-1],H[i-1][(j+1)%3])+abc[j]

print(max(H[-1]))

Submission status: Accepted

Solution code:
N = int(input().rstrip())
judge = []
for _ in range(N):
  hap_lst = list(map(int, input().rstrip().split(' ')))
  if not judge:
    judge = hap_lst
  else:
    a_0, b_0, c_0 = judge
    a_1, b_1, c_1 = hap_lst
    judge = [a_1 + max(b_0, c_0), b_1 + max(a_0, c_0), c_1 + max(a_0, b_0)]
print(max(judge))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

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

D[0] = A[0]
for i in range(1, n):
    for j in range(3):
        D[i][j] = max(D[i-1][(j+1)%3], D[i-1][(j+2)%3]) + A[i][j]
print(max(D[-1]))

Submission status: Accepted

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

A = [0]*N
B = [0]*N
C = [0]*N

for i,[a,b,c] in enumerate(abc):
  if i == 0:
    A[0],B[0],C[0] = a,b,c
  else:
    A[i] = max((B[i-1]+a),(C[i-1]+a))
    B[i] = max((A[i-1]+b),(C[i-1]+b))
    C[i] = max((A[i-1]+c),(B[i-1]+c))
  
print(max(A[-1],B[-1],C[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
init = int(pow(10, 9))
dp = [[init, init, init] for _ in range(n)]
dp[0] = list(map(int, input().split()))
for i in range(1, n):
    line = list(map(int, input().split()))
    dp[i][0] = line[0] + max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = line[1] + max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = line[2] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())
l=[[int(i) for i in input().split()] for _ in range(n)]

a,b,c=0,0,0
for x in range(n):
    pa,pb,pc=l[x]
    a,b,c=pa+max(b,c),pb+max(a,c),pc+max(b,a)

print(max(a,b,c))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
dp = [[0 for _ in range(3)] for _ in range(n)]
lis = list(map(int, input().split()))
dp[0][0] = lis[0]
dp[0][1] = lis[1]
dp[0][2] = lis[2]
for i in range(1,n):
  lis = list(map(int, input().split()))
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i][k] = max(dp[i-1][j]+lis[k], dp[i][k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

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

a,b,c = nm()

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

# i 日目に 活動 j をして夏休みを終了した
# ばあいの幸福の総和の最大値
dp = np.zeros((n, 3), dtype=np.int)
dp[0] = np.array(data[0], dtype=np.int)

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

ans = np.max(dp[n - 1])
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    import itertools
    import numpy as np

    readline = sys.stdin.readline

    N = int(readline())
    lst = [list(map(int, readline().split())) for _ in [0] * N]

    dp = np.full((N, 3), -1, np.int32)
    for i in range(N):
        for a, b in itertools.permutations([0, 1, 2], 2):
            if a == b:
                continue
            if i == 0:
                dp[i][a] = lst[i][a]
            else:
                dp[i][a] = max(dp[i][a], dp[i - 1][b] + lst[i][a])
    print(max(dp[-1]))

resolve()

Submission status: Accepted

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

for i in range(N):
  act = list(map(int,input().split()))
  for j in range(3):
    for a in range(len(act)):
      if a == j:
        continue
      if dp[i + 1][a] < dp[i][j] + act[a]:
        dp[i + 1][a] = dp[i][j] + act[a]

print(max(dp[-1]))

Submission status: Accepted

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

for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())

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

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

for i in range(1, N):
    for activity in range(3):
        for yesterday_activity in range(3):
            if yesterday_activity != activity:
                dp[i][activity] = max (
                    dp[i][activity], dp[i-1][yesterday_activity] + a[i][activity]
                )
print(max(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    abc = [None] * N

    for i in range(N):
        abc[i] = list(map(int, input().split()))
    
    dp = [[0]*3 for _ in range(N+1)]# a,b,c

    for i in range(N):
        for j in range(3):
            dp[i+1][j] = max(dp[i][(j+1)%3]+abc[i][(j+1)%3], dp[i][(j+2)%3]+abc[i][(j+2)%3])
    print(max(dp[N]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
nDays = int(input())

today = [int(x) for x in input().split()]

for i in range(nDays - 1):
    tomorrow = [int(x) for x in input().split()]
    tomorrow[0] += max(today[1], today[2])
    tomorrow[1] += max(today[0], today[2])
    tomorrow[2] += max(today[0], today[1])
    today = tomorrow

print(max(today))

Submission status: Accepted

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

print(max(dp[n-1]))
#dp[i][j]=i番目にjを選んだ時の最大値(jはa,b,cに対応している。)

Submission status: Accepted

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

print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
#dp[i][j]=i番目にjを選んだ時の最大値(jはa,b,cに対応している。)

Submission status: Accepted

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

print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
#dp[i][j]=i番目にjを選んだ時の最大値(jはa,b,cに対応している。)

Submission status: Accepted

Solution code:
d = int(input())
m=[]
for _ in range(d):
    x=list(map(int,input().split()))
    m.append(x)

dp=[[-1]*3 for i in range(d)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
n=d
for i in range(1,n):
    for j in range(3):
        dp[i][j] = max(dp[i-1][j-1]+m[i-1][j-1],dp[i-1][j-2]+m[i-1][j-2])

ans = max(dp[n-1][0]+m[n-1][0],dp[n-1][1]+m[n-1][1],dp[n-1][2]+m[n-1][2])

# print(md)
print(ans)

Submission status: Accepted

Solution code:
d = int(input())
m=[]
for _ in range(d):
    x=list(map(int,input().split()))
    m.append(x)

dp=[[-1,-1,-1] for i in range(d)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
n=d
for i in range(1,n):
    for j in range(3):
        dp[i][j] = max(dp[i-1][j-1]+m[i-1][j-1],dp[i-1][j-2]+m[i-1][j-2])

ans = max(dp[n-1][0]+m[n-1][0],dp[n-1][1]+m[n-1][1],dp[n-1][2]+m[n-1][2])

# print(md)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dp = [0, 0, 0] # last activity was A/B/C
for _ in range(n):
    ndp = [0] * 3
    d = list(map(int, input().split()))
    for i in range(3):
        ndp[i] = d[i] + max(dp[j] for j in range(3) if j != i)
    dp = ndp
print(max(dp))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ABC = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[0]*3 for _ in range(N+1)]

    for i in range(N):
        for j in range(3):
            dp[i+1][j] = max(dp[i][(j+1) % 3], dp[i][(j+2) % 3]) + ABC[i][j]

    print(max(dp[N]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0]*3 for i in range(100010)]
 
            
def chmax(a,b):
    if a>b:
        return a
    else:
        return b
 
for i in range(N):
    A,B,C=map(int,input().split())
    S[i+1][0]=A
    S[i+1][1]=B
    S[i+1][2]=C
 
DP=[[0 for j in range(3)] for i in range(100010)]
 
DP[0][0]=0
DP[0][1]=0
DP[0][2]=0
DP[1][0]=S[1][0]
DP[1][1]=S[1][1]
DP[1][2]=S[1][2]
 
if N==1:
    print(max(DP[1]))
    exit()
 
for k in range(2,N+1):
    for i in range(3):
        for j in range(3):
            if i!=j:
                DP[k][i]=chmax(DP[k-1][j]+S[k][i],DP[k][i])
                DP[k][j]=chmax(DP[k-1][i]+S[k][j],DP[k][j])
print(max(DP[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N; B = [0]*N; C = [0]*N
for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

lisA = [0]*N; lisB = [0]*N; lisC = [0]*N
lisA[0] = A[0]; lisB[0] = B[0]; lisC[0] = C[0];
for i in range(1, N):
    lisA[i] = max(lisB[i-1], lisC[i-1]) + A[i]
    lisB[i] = max(lisA[i-1], lisC[i-1]) + B[i]
    lisC[i] = max(lisA[i-1], lisB[i-1]) + C[i]

print(max(lisA[N-1], lisB[N-1], lisC[N-1]))

Submission status: Accepted

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_c
N = int(input())
Max_List = [[0] * 3 for i in range(N)]
for i in range(N):
    Current_List = list(map(int,input().split()))  
    if i == 0:
        Max_List[i] = Current_List
    else:
        Search_List = Max_List[i-1]
        for j in range(3):
            Current_Search_List = Search_List[1:3]
            Max_List[i][j] = max(Current_Search_List) + Current_List[j]
            Search_List.append(Search_List[0])
            del Search_List[0]
        

        
print(max(Max_List[-1]))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_c
N = int(input())
Max_List = [[0] * 3] * N
for i in range(N):
    Current_List = list(map(int,input().split()))  
    if i == 0:
        Max_List[i] = Current_List
    else:
        Search_List = Max_List[i-1]
        Current_Max_List = []
        for j in range(3):
            Current_Search_List=Search_List[1:3]
            Current_Max_List.append(max(Current_Search_List) + Current_List[j])
            Search_List.append(Search_List[0])
            del Search_List[0]
        
        Max_List[i] = Current_Max_List

        
print(max(Max_List[-1]))

Submission status: Accepted

Solution code:
n=int(input())
a,b,c=[],[],[]
for i in range(n):
  a1,b1,c1=map(int,input().split())
  a+=[a1]
  b+=[b1]
  c+=[c1]

hp=[[0 for j in range(n)]for i in range(3)]
hp[0][0],hp[1][0],hp[2][0]=a[0],b[0],c[0]

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

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

Submission status: Accepted

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

N = int(readline())
dp = [[0] * 3 for i in range(N + 1)]

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

Submission status: Accepted

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

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

# i日目にjを選択した時の最大値を計算する
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j] = array[i][j]
            continue
        for k in range(3):
            if j != k:
                sum = dp[i - 1][k] + array[i][j]
                dp[i][j] = sum if sum > dp[i][j] else dp[i][j]

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

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  dp=[[0,0,0]]
  for i in range(1,n+1):
    a,b,c=map(int,input().split())
    dp.append([max(dp[i-1][1],dp[i-1][2])+a,max(dp[i-1][0],dp[i-1][2])+b,max(dp[i-1][0],dp[i-1][1])+c])
    #print(dp)
  print(max(dp[n]))
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_c
N = int(input())
Max_List=[]
N_List=[i for i in range(3)]
for i in range(N):
    Current_List=list(map(int,input().split())) 
    if i == 0:
        Max_List.append(Current_List)
    else:
        Current_Max_List = []
        Search_List=Max_List[i-1]
        for j in range(3):
            Current_Search_List=Search_List[1:3]
            Current_Max_List.append(max(Current_Search_List)+Current_List[j])
            Search_List.append(Search_List[0])
            del Search_List[0]
        Max_List.append(Current_Max_List)
        
    
print(max(Max_List[-1]))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_c
import numpy as np
N = int(input())
Max_List=[]
N_List=[i for i in range(3)]
for i in range(N):
    Current_List=list(map(int,input().split())) 
    if i == 0:
        Max_List.append(Current_List)
    else:
        Current_Max_List = []
        for j in range(3):
            Index_List=np.array(Max_List[i-1])
            ind = np.ones(3, dtype=bool)
            ind[j] = False
            Current_Max_List.append(max(Index_List[ind])+Current_List[j])
            
        Max_List.append(Current_Max_List)
        
    
print(max(Max_List[-1]))

Submission status: Accepted

Solution code:
# C_vacation
N = int( input() )
happiness = list()
for nn in range(N):
    h = [int(x) for x in input().split()]
    happiness.append( h )

dp = [[0]*3 for x in range(N)]
dp[0] = happiness[0]
for nn in range(1, N):
    for ii in range(3): # day nn's choice
        max_reward = 0
        for jj in range(3): # day (nn-1)'s choice
            r = dp[nn-1][jj] + happiness[nn][ii]
            if( ii != jj and r > max_reward ):
                max_reward = r
        dp[nn][ii] = max_reward

ans = 0
for ii in range(3):
    if( dp[-1][ii] > ans ):
        ans = dp[-1][ii]
print( ans )

Submission status: Accepted

Solution code:
n = int(input())
x = [0] * n
#x = [[0]*3 for i in range(n)]

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

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

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

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

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

print(ans)