結果
問題 | No.572 妖精の演奏 |
ユーザー | roaris |
提出日時 | 2019-12-18 14:00:25 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,512 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 87,040 KB |
実行使用メモリ | 86,148 KB |
最終ジャッジ日時 | 2023-09-20 13:36:55 |
合計ジャッジ時間 | 5,331 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 128 ms
78,404 KB |
testcase_01 | AC | 135 ms
79,300 KB |
testcase_02 | WA | - |
testcase_03 | AC | 122 ms
78,728 KB |
testcase_04 | AC | 118 ms
78,492 KB |
testcase_05 | WA | - |
testcase_06 | AC | 164 ms
80,048 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 240 ms
85,180 KB |
testcase_11 | AC | 300 ms
85,828 KB |
testcase_12 | WA | - |
testcase_13 | AC | 243 ms
85,656 KB |
testcase_14 | WA | - |
testcase_15 | AC | 238 ms
85,536 KB |
testcase_16 | AC | 239 ms
85,804 KB |
testcase_17 | AC | 243 ms
85,532 KB |
testcase_18 | WA | - |
testcase_19 | AC | 109 ms
78,060 KB |
ソースコード
import sys sys.setrecursionlimit(10000) def rec(i, j, k): if memo[i][j][k]!=-1: return memo[i][j][k] if i==0: memo[i][j][k] = A[j][k] return A[j][k] res = 0 for l in range(m): if res<A[j][k]+rec(i-1, k, l): res = A[j][k]+rec(i-1, k, l) to[V-i][j][k] = (k, l) memo[i][j][k] = res return res n = int(input()) n -= 1 m = int(input()) A = [list(map(int, input().split())) for _ in range(m)] V = m+100 memo = [[[-1]*m for _ in range(m)] for _ in range(V+1)] to = [[[0]*m for _ in range(m)] for _ in range(V)] for i in range(m): for j in range(m): rec(V, i, j) ans = 0 for i in range(m): for j in range(m): flag = [[-1]*m for _ in range(m)] cur_i, cur_j = i, j cnt = 0 flag[cur_i][cur_j] = cnt scores = [A[cur_i][cur_j]] while True: cur_i, cur_j = to[cnt][cur_i][cur_j] #print(cur_i, cur_j) if flag[cur_i][cur_j]>=0: #print(scores) ini = flag[cur_i][cur_j] loop = cnt+1-flag[cur_i][cur_j] #print(ini, loop) s1 = sum(scores[:ini]) s2 = sum(scores[ini:]) ans = max(ans, s1+(n-ini)//loop*s2+sum(scores[ini:ini+(n-ini)%loop])) break cnt += 1 flag[cur_i][cur_j] = cnt scores.append(A[cur_i][cur_j]) print(ans)