Editorial for Đi ngang qua ô lưới bản khó

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: hazzu

import sys
try :
    TASKNAME = "D"
    sys.stdin = open(TASKNAME + ".inp", "r")
    sys.stdout = open(TASKNAME + ".out", "w")
except :
    sys.stdin = sys.__stdin__
    sys.stdout = sys.__stdout__

n = int(input())
a = [input() for i in range(3)]

val = [[[[0] * n for i in range(n)] for j in range(3)] for k in range(2)]
for r in range(3):
    for i in range(n):
        sum = 0
        for j in range(i, n):
            sum = (sum << 1) + (a[r][j] == '1')
            val[0][r][i][j] = sum
        sum = 0
        for j in range(i, -1, -1):
            sum = (sum << 1) + (a[r][j] == '1')
            val[1][r][j][i] = sum

dp = [[0] * 2 for i in range(n + 1)]
dp[0][0] = -(2**301)

for i in range(1, n + 1):
    for j in range(i, 0, -1):
        path0 = val[0][0][j - 1][i - 1]
        path1 = val[1][1][j - 1][i - 1]
        path2 = val[0][2][j - 1][i - 1]

        cost1 = (((path2 << (i - j + 1)) + path1) << (i - j + 1)) + path0
        dp[i][1] = max(dp[i][1], (dp[j - 1][0] << 3 * (i - j + 1)) + cost1)

        cost0 = (((path0 << (i - j + 1)) + path1) << (i - j + 1)) + path2
        dp[i][0] = max(dp[i][0], (dp[j - 1][1] << 3 * (i - j + 1)) + cost0)

print(max(dp[n]))

Editorial for Đi ngang qua ô lưới bản khó

Comments