ソースコード
#include<bits/stdc++.h>
using namespace std;
#define INF 184497440737095
long long N, a[20][20], t[20], temp[20][20], mimi= INF;
int data[20][20];
long long foo(long long int te[],long long int x, long long tt){//cout<<endl<<x<<endl;
if(x > N-1){ mimi = min(mimi, tt);return 0;}
if(tt >= mimi)return INF;
long long ans = INF, te2[20] = {}, te3[20]={};
long long co=0, te4;
for(int i = 0; i < N; i++){//cout<<te[i]<<endl;
te2[i]=te[i];
if(te[i]==1)te3[co++] = i;
}
for(int i = 0; i < N; i++){
if(te[i]==1)continue;
int ma = 0;
for(int j = 0; j < co; j++){//cout<<" "<<j<<" "<<i<<" "<<a[j][i]<<endl;
ma+=a[te3[j]][i];
}//cout<<endl;
te4 =t[i]-ma;
//if(te4+tt >= mimi)continue;
//cout<<te4<<" "<<t[i]<<" "<<i<<" "<<ma<<endl;
te2[i]=1;
ans = min(foo(te2, x+1, te4+tt)+te4, ans);
te2[i]=0;
}
if(ans==0)ans = INF;
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];
}
}
/*for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
int ma = 0;
for(int k = 0; k < j; k++){
if(ma < a[k][j])ma=a[k][j];
}
}
}*/
long long int te[20] = {};
cout<<foo(te, 0, 0)<<endl;
return 0;
}