結果

提出番号 2202
提出者 hamuhei4869
言語 C++
提出日時 2019-02-09 00:57:17
問題名 (70)アルゴリズムのお勉強
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8080KB
2 AC 100% 2ms 7888KB
3 AC 100% 2ms 8144KB
4 AC 100% 2ms 7952KB
5 AC 100% 2ms 8512KB
6 AC 100% 2ms 8448KB
7 AC 100% 2ms 8160KB
8 AC 100% 2ms 8400KB
9 AC 100% 2ms 8560KB
10 AC 100% 2ms 8096KB
11 AC 100% 3ms 7856KB
12 AC 100% 2ms 8336KB
13 WA 0% 3ms 8112KB
14 AC 100% 2ms 8336KB
15 WA 0% 2ms 8512KB
16 AC 100% 2ms 7872KB
17 AC 100% 2ms 8096KB
18 AC 100% 2ms 8752KB
19 AC 100% 4ms 7936KB
20 AC 100% 5ms 8608KB
21 AC 100% 2ms 7888KB
22 AC 100% 8ms 7952KB
23 AC 100% 2ms 8112KB
24 AC 100% 18ms 8320KB
25 AC 100% 5ms 8416KB
26 WA 0% 8ms 7936KB
27 AC 100% 18ms 8112KB
28 AC 100% 4ms 8176KB
29 WA 0% 92ms 18032KB
30 AC 100% 8ms 7872KB

ソースコード

#include <bits/stdc++.h>
using LL = long long;
const LL MOD = 1e9+9;
using namespace std;


vector<vector<int>> dp;
vector<int> task;
vector<vector<int>> Edge;
int N;
int calc(int bit, int now){
 //   cout<<bitset<10>(bit)<<endl;
    if(bit == (1<<N)-1){
        return 0;
    }
    if(dp[bit][now] != 1e9){
        return dp[bit][now];
    }
    for(int a = 0;a < N;a++){
        if(a == now)continue;
        if(!((1<<a)&bit)){
            int totalmi = 0;
            for(int b = 0;b < N;b++){
                if(bit & (1<<b)){
                    totalmi += Edge.at(a).at(b);
                }
            }
            dp[bit][now] = min(calc(bit | (1<<a),a) + max(0,task.at(a)-totalmi),dp[bit][now]);
        }
    }
    return dp[bit][now];
}
int main(){
    cin >> N;
    for(int a = 0;a < N;a++){
        int b;cin >> b;
        task.push_back(b);
    }
    dp = vector<vector<int>>((1<<N)+1,vector<int>(N,1e9));
    for(int a = 0;a < N;a++){
        vector<int> uku;
        for(int b = 0;b < N;b++){
            int c;cin >> c;
            uku.push_back(c);
        }
        Edge.push_back(uku);
    }
    int ans = 1e9;
    for(int a = 0;a < N;a++){
        ans = min(ans, calc(0 | (1<<a),a)+task.at(a));
       // cout<<ans<<endl;
    }
    cout<<ans<<endl;
}