ソースコード
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
auto& in = std::cin;
auto& out = std::cout;
int32_t N;
int32_t cost[16];
int32_t minus[16][16];
int32_t dp[1 << 16];
template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
for (auto& i : arr) {
fill_all(i, v);
}
}
int32_t func(std::bitset<16> mask)
{
if (mask == 0) { return 0; }
if (dp[mask.to_ulong()] != -1) {
return dp[mask.to_ulong()];
}
int32_t cost2[16] = {};
for (int32_t i = 0; i < N; i++){
cost2[i] = cost[i];
}
for (int32_t i = 0; i < N; i++)
{
if (!mask[i]) {
for (int32_t j = 0; j < N; j++) {
cost2[j] = std::max(0, cost2[j] - minus[i][j]);
}
}
}
int32_t res = 10001616;
for (int32_t i = 0; i < N; i++)
{
if (mask[i]) {
mask[i] = false;
res = std::min(res, func(mask)+cost2[i]);
mask[i] = true;
}
}
return dp[mask.to_ulong()] = res;
}
int main()
{
using std::endl;
in.sync_with_stdio(false);
out.sync_with_stdio(false);
in.tie(nullptr);
out.tie(nullptr);
fill_all(dp, -1);
in >> N;
for (int32_t i = 0; i < N; i++)
{
in >> cost[i];
}
for (int32_t i = 0; i < N; i++)
for (int32_t j = 0; j < N; j++)
{
in >> minus[i][j];
}
out << func((1 << N) - 1) << endl;;
return 0;
}
#endif