提出番号 | 2290 |
---|---|

提出者 | ne0n |

言語 | Python3 |

提出日時 | 2019-12-07 22:45:06 |

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

結果 | TLE |

点数 | 0% |

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

1 | AC | 100% | 45ms | 32592KB |

2 | AC | 100% | 26ms | 33104KB |

3 | AC | 100% | 45ms | 33232KB |

4 | AC | 100% | 24ms | 32640KB |

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

6 | AC | 100% | 1571ms | 32720KB |

7 | AC | 100% | 46ms | 33008KB |

8 | AC | 100% | 24ms | 33248KB |

9 | AC | 100% | 25ms | 32720KB |

10 | AC | 100% | 44ms | 32976KB |

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

12 | TLE | 0% | 15744ms | 33088KB |

13 | TLE | 0% | 20003ms | 0KB |

14 | TLE | 0% | 15848ms | 33088KB |

15 | TLE | 0% | 15574ms | 32976KB |

16 | AC | 100% | 200ms | 33184KB |

17 | AC | 100% | 45ms | 33008KB |

18 | AC | 100% | 42ms | 32800KB |

19 | TLE | 0% | 20003ms | 0KB |

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

21 | AC | 100% | 197ms | 32592KB |

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

23 | AC | 100% | 1578ms | 32768KB |

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 |

```
n = int(input())
t = list(map(int,input().split()))
a = list()
dp = [10000 for i in range(2**n)]
for i in range(n):
a.append(list(map(int,input().split())))
oo = "0"*n
#for i in range(n):
# omae = oo[:i] + "1" + oo[i+1:]
# omae_int = 0
# for j in range(n):
# omae_int += 2**j*int(omae[-1*(j+1)])
# dp[omae_int] = 0
dp[0] = 0
def func(name):
for i in range(n):
if name == "1"*n:
break
if name[i] == "1":
continue
add = 0
for j in range(n):
if name[j] == "1":
add += a[-1*(j+1)][-1*(i+1)]
after = name
after = after[:i] +"1"+after[i+1:]
after_int = 0
name_int = 0
for j in range(n):
after_int += (2**j)*int(after[-1*(j+1)])
name_int += (2**j)*int(name[-1*(j+1)])
if t[i]-add > 0:
dp[after_int] = min(dp[after_int],dp[name_int] + t[i] - add)
else:
dp[after_int] = min(dp[after_int],dp[name_int])
func(after)
omae = "0"*n
func(omae)
print(dp[2**n-1])
```