結果

提出番号 2160
提出者 kage
言語 C++
提出日時 2018-08-14 09:26:22
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 1ms 8240KB
2 AC 100% 2ms 8128KB
3 AC 100% 2ms 8736KB
4 AC 100% 2ms 7824KB
5 AC 100% 1ms 7760KB
6 AC 100% 2ms 8432KB
7 AC 100% 1ms 8048KB
8 AC 100% 2ms 7792KB
9 AC 100% 2ms 8048KB
10 AC 100% 2ms 8000KB
11 AC 100% 2ms 7968KB
12 AC 100% 2ms 7536KB
13 AC 100% 2ms 7600KB
14 AC 100% 2ms 8432KB
15 AC 100% 2ms 8384KB
16 AC 100% 2ms 8128KB
17 AC 100% 2ms 7984KB
18 AC 100% 1ms 8032KB
19 AC 100% 2ms 8688KB
20 AC 100% 2ms 8224KB
21 AC 100% 2ms 8384KB
22 AC 100% 3ms 8192KB
23 AC 100% 2ms 7776KB
24 AC 100% 4ms 8432KB
25 AC 100% 2ms 7472KB
26 AC 100% 2ms 8672KB
27 AC 100% 4ms 7776KB
28 AC 100% 2ms 8416KB
29 AC 100% 12ms 7632KB
30 AC 100% 3ms 7168KB

ソースコード

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<28)-1
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, t[16], a[16][16], dp[1<<16];
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n;
    rep(i, 0, n) cin >> t[i];
    rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
    rep(i, 0, 1<<n) dp[i] = INF;
    dp[0] = 0;
    rep(i, 0, 1<<n) {
        rep(j, 0, n) {
            if (!(i & (1 << j))) {
                int tmp = t[j];
                rep(k, 0, n) {
                    if (!(i & (1<<k))) tmp -= a[k][j];
                }
                chmin(dp[i+(1<<j)], dp[i]+tmp);
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;
    return 0;
}