結果

提出番号 2175
提出者 daleksprinter
言語 C++
提出日時 2018-10-03 14:42:17
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8736KB
2 AC 100% 2ms 8432KB
3 AC 100% 2ms 8224KB
4 AC 100% 2ms 8160KB
5 AC 100% 2ms 7808KB
6 AC 100% 2ms 8208KB
7 AC 100% 2ms 8656KB
8 AC 100% 2ms 8240KB
9 AC 100% 2ms 8192KB
10 AC 100% 2ms 8304KB
11 AC 100% 2ms 7632KB
12 AC 100% 2ms 8112KB
13 AC 100% 2ms 8000KB
14 AC 100% 2ms 8736KB
15 AC 100% 2ms 8432KB
16 AC 100% 2ms 7632KB
17 AC 100% 2ms 7888KB
18 AC 100% 2ms 8576KB
19 AC 100% 3ms 8432KB
20 AC 100% 3ms 8480KB
21 AC 100% 2ms 8448KB
22 AC 100% 3ms 8208KB
23 AC 100% 2ms 7568KB
24 AC 100% 4ms 8496KB
25 AC 100% 2ms 8176KB
26 AC 100% 3ms 7968KB
27 AC 100% 4ms 8528KB
28 AC 100% 2ms 8448KB
29 AC 100% 13ms 8416KB
30 AC 100% 3ms 7536KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

//macro-----------------------------------------------------------------------------------------
#define rep(i,a) for(int i=0;i<a;i++)
#define revrep(i,a,b) for(int i=a;i>b;i--)
#define int long long
#define sort(arr) sort(arr.begin(), arr.end())
#define reverse(arr) reverse(arr.begin(), arr.end())
#define elif else if

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pi;

//constant--------------------------------------------------------------------------------------
const int inf = 100100100100000;
const int mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//general_method--------------------------------------------------------------------------------
vector<int> cs(vector<int> arr){vector<int> ret = arr;rep(i,arr.size()){ret[i] += ret[i-1];}return ret;}
int ceil(int a, int b){if(a%b == 0) return a/b;else return a/b + 1;}
int digitlen(int i){int t = i;int count = 0;while(t){count += 1;t /= 10;}return count;}
int gcd(int a, int b){if(b== 0)return a;return gcd(b, a%b);}


//io_method-------------------------------------------------------------------------------------
int input(){int tmp;cin >> tmp;return tmp;}

void print(vi arr){
    
    rep(i,arr.size()) cout << arr[i] << " "; cout << endl;
}
void print(int n){
    cout << n << endl;
}
//main------------------------------------------------------------------------------------------

int n;
vi t;
vvi arr(16);
vi dp((1<<16),-1);

int dfs(int s){
    if(dp[s] > -1) return dp[s];

    if(s == ((1<<n)-1)) return 0;

    int ret = inf;
    rep(i,n){
        if(!(s & (1 << i))){
            int tmp = t[i];
            rep(j,n){
                if(s & (1 << j)){
                    tmp -= arr[i][j];
                }
            }
            tmp += dfs(s + (1 << i));
            ret = min(ret, tmp);
        }
        
    }
    
    return dp[s] = ret;
    

}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    
    n = input();
    rep(i,n) t.push_back(input());
    rep(i,n) rep(j,n) arr[i].push_back(input());

    

    print(dfs(0));





}