提出番号 | 2413 |
---|---|

提出者 | awk_138 |

言語 | Python3 |

提出日時 | 2020-10-24 19:23:30 |

問題名 | (70)アルゴリズムのお勉強 |

結果 | WA |

点数 | 0% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | WA | 0% | 21ms | 33104KB |

2 | WA | 0% | 21ms | 32720KB |

3 | WA | 0% | 22ms | 33264KB |

4 | WA | 0% | 25ms | 32928KB |

5 | WA | 0% | 21ms | 32912KB |

6 | WA | 0% | 26ms | 33168KB |

7 | WA | 0% | 21ms | 32992KB |

8 | WA | 0% | 31ms | 33024KB |

9 | WA | 0% | 20ms | 32624KB |

10 | WA | 0% | 21ms | 33008KB |

11 | WA | 0% | 52ms | 34992KB |

12 | WA | 0% | 33ms | 34160KB |

13 | WA | 0% | 52ms | 35104KB |

14 | WA | 0% | 34ms | 33952KB |

15 | WA | 0% | 33ms | 35216KB |

16 | WA | 0% | 22ms | 32816KB |

17 | WA | 0% | 22ms | 33072KB |

18 | WA | 0% | 21ms | 33008KB |

19 | WA | 0% | 91ms | 36032KB |

20 | WA | 0% | 93ms | 36272KB |

21 | WA | 0% | 23ms | 32800KB |

22 | WA | 0% | 184ms | 37376KB |

23 | WA | 0% | 26ms | 33392KB |

24 | WA | 0% | 403ms | 43088KB |

25 | WA | 0% | 99ms | 35760KB |

26 | WA | 0% | 188ms | 38736KB |

27 | WA | 0% | 410ms | 43312KB |

28 | WA | 0% | 91ms | 35936KB |

29 | TLE | 0% | 2021ms | 80832KB |

30 | WA | 0% | 185ms | 38656KB |

```
def rec(bit, v, dist, dp, N):
if dp[bit][v] != -1:
return dp[bit][v]
if bit == (1<<v):
dp[bit][v] = 0
return dp[bit][v]
res = -float('inf')
prev_bit = bit & ~(1<<v)
for u in range(N):
if not(prev_bit & (1<<u)):
continue
res = max(res, rec(prev_bit, u, dist, dp, N) + dist[u][v])
if v == 0:
print(rec(prev_bit, u, dist, dp, N))
print(dist[u][v])
dp[bit][v] = res
return res
def solve():
N = int(input())
t = list(map(int, input().split()))
dist = [list(map(int,input().split())) for _ in range(N)]
res = -float('inf')
dp = [[-1] * N for _ in range((1<<N))]
for v in range(N):
res = max(res, rec((1<<N)-1, v, dist, dp, N))
print(max(0,sum(t) - res))
if __name__ == '__main__':
solve()
```