提出番号 | 2426 |
---|---|

提出者 | Focus_Sash |

言語 | C++ |

提出日時 | 2021-04-27 19:03:21 |

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

結果 | WA |

点数 | 0% |

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

1 | WA | 0% | 3ms | 7504KB |

2 | WA | 0% | 2ms | 7968KB |

3 | WA | 0% | 3ms | 8032KB |

4 | WA | 0% | 3ms | 7792KB |

5 | WA | 0% | 3ms | 8480KB |

6 | WA | 0% | 2ms | 8112KB |

7 | WA | 0% | 2ms | 8544KB |

8 | WA | 0% | 2ms | 7872KB |

9 | WA | 0% | 2ms | 7856KB |

10 | WA | 0% | 2ms | 7872KB |

11 | WA | 0% | 2ms | 7872KB |

12 | WA | 0% | 2ms | 7888KB |

13 | WA | 0% | 2ms | 8096KB |

14 | WA | 0% | 2ms | 8112KB |

15 | WA | 0% | 2ms | 7872KB |

16 | WA | 0% | 2ms | 7872KB |

17 | WA | 0% | 2ms | 7872KB |

18 | WA | 0% | 2ms | 8512KB |

19 | WA | 0% | 2ms | 8560KB |

20 | WA | 0% | 2ms | 7872KB |

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

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

23 | WA | 0% | 2ms | 7600KB |

24 | WA | 0% | 4ms | 7600KB |

25 | WA | 0% | 2ms | 8096KB |

26 | WA | 0% | 3ms | 8016KB |

27 | WA | 0% | 4ms | 8112KB |

28 | WA | 0% | 2ms | 8112KB |

29 | WA | 0% | 13ms | 8448KB |

30 | WA | 0% | 3ms | 8512KB |

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define V vector
const ll INF = 1000000000000000001;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
ll n; cin >> n;
vl t(n); rep(i,n) cin >> t[i];
V<vl> a(n, vl(n));
rep(i,n) rep(j,n) cin >> a[i][j];
vl dp(1<<n, INF);
dp[0] = 0;
rep(S, 1<<n){
rep(i, n){
if(S & (1<<i)) continue;
ll red = 0;
rep(j,n){
if(S & (1<<j)) red += a[j][i];
}
dp[S|(1<<i)] = max(dp[S|(1<<i)], dp[S] + t[i] - red);
}
}
cout << dp[(1<<n)-1] << '\n';
return 0;
}
```