ソースコード
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while(true)
////1
//int main() {
// int f, s;
// cin >> f >> s;
// bool ans = true;
// while (f >= 2 && s >= 1) {
// f -= 2;
// s -= 1;
// ans = !ans;
// }
// if (ans) cout << "K" << endl;
// else cout << "O" << endl;
//
// return 0;
//}
////2
//int main() {
// int N, M;
// cin >> N >> M;
// vector<int> A;
// for (int i = 0; i < N; i++) {
// int tmp;
// cin >> tmp;
// A.push_back(tmp);
// }
// sort(A.begin(), A.end());
// reverse(A.begin(), A.end());
//
// int ans = 0;
// int tmp = 0;
// while (tmp < M) {
// tmp += A[ans];
// ans++;
// }
// cout << ans << endl;
//
// return 0;
//}
////3
//int main() {
// int N, H, W;
// cin >> N >> H >> W;
// vector<string> f;
// for (int i = 0; i < H; i++) {
// string tmp;
// cin >> tmp;
// f.push_back(tmp);
// }
//
// for (int i = 1; i <= N; i++) {
// //横
// int ans1 = 0;
// for (int j = 0; j < H; j++) {
// for (int k = 0; k < W; k++) {
// if (k + i > W) break;
// bool tmp = true;
// for (int l = k; l < k + i; l++) {
// if (f[j][l] == '#') tmp = false;
// }
// if (tmp) {
// ans1++;
// k += i - 1;
// }
// }
// }
//
// //縦
// int ans2 = 0;
// //for (int j = 0; j < W; j++) {
// // for (int k = 0; k < H; k++) {
// // if (k + i > H) break;
// // bool tmp = true;
// // for (int l = k; l < k + i; l++) {
// // if (f[l][j] == '#') tmp = false;
// // }
// // if (tmp) {
// // ans2++;
// // k += i - 1;
// // }
// // }
// //}
//
// cout << max(ans1, ans2) << endl;
// }
//
// return 0;
//}
//4
int N;
int t[16];
int a[16][16];
map<vector<bool>, int> dp;
int solve(vector<bool> state) {
if (dp.count(state) == 1) return dp[state];
int ans = INT_MAX;
for (int i = 0; i < N; i++) {
if (state[i]) continue;
int less = 0;
for (int j = 0; j < N; j++) {
if (state[j]) less += a[j][i];
}
state[i] = true;
ans = min(ans, t[i] - less + solve(state));
state[i] = false;
}
dp[state] = ans;
return ans;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> t[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> a[i][j];
}
}
vector<bool> state;
vector<bool> state2;
for (int i = 0; i < N; i++) {
state.push_back(false);
state2.push_back(true);
}
dp[state2] = 0;
cout << solve(state) << endl;
return 0;
}
////5
//int main() {
//
//
// return 0;
//}
////6
//int main() {
//
//
// return 0;
//}
////7
//int main() {
//
//
// return 0;
//}
////8
//int main() {
//
//
// return 0;
//}
////9
//int main() {
//
//
// return 0;
//}
////10
//int main() {
//
//
// return 0;
//}