Участник:Bagurgl/Max sum Min sum

Материал из DISCOPAL
< Участник:Bagurgl
Версия от 15:17, 19 марта 2021; Bagurgl (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://www.codechef.com/problems/DYNMCPRG/

 
def find_max_sum(array):
    buf_subseq = 0
    sum_subseq = 0
    for i in range(len(array)):
        tmp_subseq = max(sum_subseq, array[i] + buf_subseq)
        buf_subseq = sum_subseq
        sum_subseq = tmp_subseq
    return sum_subseq
 
 
t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    max_sum = []
    tets_arr = []
    for j in range(n):
        tmp = list(map(int, input().split()))
        max_sub = find_max_sum(tmp)
        max_sum.append(max_sub)
    if n == 1:
        print(max_sum[0])
    elif n == 2:
        print(min(max_sum[0], max_sum[1]))
    elif n == 3:
        print(min(max_sum[1], max_sum[0] + max_sum[2]))
    else:
        print(min(max_sum[0] + max_sum[2], min(max_sum[1] + max_sum[3], max_sum[0] + max_sum[3])))