제출 #1132036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132036		krishnaar2305	Sailing Race (CEOI12_race)	Pypy 3	0 / 100	3100 ms	102332 KiB

race

import sys

# Constants
MAXN = 505
INF = int(1e9)

# Global variables
edge = [[0] * MAXN for _ in range(MAXN)]
dp = [[[0, 0] for _ in range(MAXN)] for _ in range(MAXN)]
dp1 = [[[0, 0] for _ in range(MAXN)] for _ in range(MAXN)]
nx = [[0, 0] for _ in range(MAXN)]
n = 0
type_ = 0

def solve(l, r, x):
    if edge[l][r]:
        dp[l][r][x] = 1
        dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1]
    else:
        dp[l][r][x] = -n
        dp1[l][r][x] = -n
    
    m = nx[l][x]
    while m != r:
        dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x])
        dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x])
        m = nx[m][x]
    
    dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x])

def main():
    global n, type_
    n, type_ = map(int, input().split())
    
    for i in range(n):
        data = list(map(int, input().split()))
        idx = 0
        while data[idx] != 0:
            edge[i][data[idx] - 1] = 1
            idx += 1
        
        nx[i][0] = (i + 1) % n
        nx[i][1] = (i + n - 1) % n
    
    for d in range(1, n):
        for l in range(n):
            r = (l + d) % n
            solve(l, r, 0)
            solve(r, l, 1)
    
    ans = (-1, 0)
    for l in range(n):
        for r in range(n):
            for x in range(2):
                ans = max(ans, (dp1[l][r][x], l + 1))
    
    if type_:
        for l in range(n):
            for r in range(n):
                for x in range(2):
                    if dp[l][r][x] <= 0:
                        continue
                    st = nx[r][x]
                    while st != l and edge[st][l] == 0:
                        st = nx[st][x]
                    if st == l:
                        continue
                    ed = nx[st][x]
                    while ed != l:
                        if edge[r][ed]:
                            ans = max(ans, (max(dp1[ed][nx[l][x ^ 1]][x], dp1[ed][nx[st][x]][x ^ 1]) + 2 + dp[l][r][x], st + 1))
                        ed = nx[ed][x]
    
    print(ans[0])
    # print(ans[1])

if __name__ == '__main__':
    main()

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'race.py'...

=======
  adding: __main__.pyc (deflated 56%)

=======

• Subtask 1: 0 / 100