結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 2ms 8544KB
2 WA 0% 2ms 8160KB
3 WA 0% 2ms 8560KB
4 WA 0% 2ms 8112KB
5 WA 0% 2ms 7840KB
6 WA 0% 2ms 8416KB
7 WA 0% 2ms 8080KB
8 AC 100% 2ms 8368KB
9 WA 0% 2ms 7888KB
10 WA 0% 2ms 7872KB
11 WA 0% 2ms 7840KB
12 WA 0% 2ms 8400KB
13 WA 0% 2ms 7936KB
14 WA 0% 2ms 8400KB
15 WA 0% 2ms 8176KB
16 WA 0% 2ms 8336KB
17 WA 0% 2ms 8128KB
18 WA 0% 2ms 8528KB
19 WA 0% 2ms 8512KB
20 WA 0% 2ms 8544KB
21 WA 0% 2ms 8064KB
22 WA 0% 2ms 8336KB
23 WA 0% 2ms 8384KB
24 WA 0% 2ms 7872KB
25 WA 0% 2ms 7872KB
26 WA 0% 8ms 8480KB
27 WA 0% 2ms 8128KB
28 WA 0% 2ms 7872KB
29 WA 0% 5ms 18032KB
30 WA 0% 2ms 8432KB

ソースコード

#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(b).at(a);
                }
            }
            return dp[bit][now] = calc(bit | (1<<a),a) + max(0,task.at(a)-totalmi);
        }
    }
}
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;
}