提出番号 | 2333 |
---|---|

提出者 | efunyo |

言語 | Python3 |

提出日時 | 2020-03-24 22:11:09 |

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

結果 | TLE |

点数 | 0% |

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

1 | AC | 100% | 34ms | 35104KB |

2 | AC | 100% | 25ms | 34688KB |

3 | AC | 100% | 32ms | 34400KB |

4 | AC | 100% | 26ms | 35088KB |

5 | AC | 100% | 28ms | 34816KB |

6 | AC | 100% | 433ms | 34704KB |

7 | AC | 100% | 32ms | 34944KB |

8 | AC | 100% | 27ms | 35264KB |

9 | AC | 100% | 27ms | 34944KB |

10 | AC | 100% | 31ms | 35120KB |

11 | TLE | 0% | 20002ms | 0KB |

12 | TLE | 0% | 4045ms | 34592KB |

13 | TLE | 0% | 20002ms | 0KB |

14 | TLE | 0% | 3991ms | 34416KB |

15 | TLE | 0% | 3623ms | 35008KB |

16 | AC | 100% | 74ms | 35136KB |

17 | AC | 100% | 31ms | 35088KB |

18 | AC | 100% | 32ms | 34400KB |

19 | TLE | 0% | 20002ms | 0KB |

20 | TLE | 0% | 20002ms | 0KB |

21 | AC | 100% | 67ms | 34704KB |

22 | TLE | 0% | 20002ms | 0KB |

23 | AC | 100% | 435ms | 34656KB |

24 | TLE | 0% | 20002ms | 0KB |

25 | TLE | 0% | 20002ms | 0KB |

26 | TLE | 0% | 20002ms | 0KB |

27 | TLE | 0% | 20002ms | 0KB |

28 | TLE | 0% | 20002ms | 0KB |

29 | TLE | 0% | 20002ms | 0KB |

30 | TLE | 0% | 20002ms | 0KB |

```
#https://kotamanegi.com/Problems/view/index.php?page=70
def main():
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate
#from itertools import product
from bisect import bisect_left,bisect_right
import heapq
from math import floor, ceil
#from operator import itemgetter
#inf = 10**17
#mod = 10**9 + 7
N = int(input())
t = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(N)]
inf = 10**6
#dp[s]:sは学習済みのアルゴリズム
# dp[s]はその時かかっている時間
dp = [inf]*(1<<N)
dp[0] = 0
def dfs(s):
for i in range(N):
if (s>>i) & 1:
continue
hiku = 0
for j in range(N):
if (s>>j) & 1:
hiku += a[j][i]
ns = s |1<<i
dp[ns] = min(dp[ns], dp[s]+t[i]-hiku)
dfs(ns)
dfs(0)
print(dp[-1])
if __name__ == '__main__':
main()
```