結果

提出番号 2205
提出者 matsukin1111
言語 C++
提出日時 2019-02-21 18:38:18
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8176KB
2 AC 100% 2ms 7872KB
3 AC 100% 2ms 8464KB
4 AC 100% 2ms 7840KB
5 AC 100% 2ms 7888KB
6 AC 100% 2ms 8448KB
7 AC 100% 2ms 8336KB
8 AC 100% 2ms 8336KB
9 AC 100% 2ms 7856KB
10 AC 100% 2ms 8016KB
11 AC 100% 2ms 8448KB
12 AC 100% 2ms 8160KB
13 AC 100% 2ms 7872KB
14 AC 100% 2ms 8096KB
15 AC 100% 2ms 8064KB
16 AC 100% 2ms 7872KB
17 AC 100% 2ms 8784KB
18 AC 100% 2ms 8128KB
19 AC 100% 2ms 8320KB
20 AC 100% 2ms 8080KB
21 AC 100% 2ms 7888KB
22 AC 100% 3ms 7840KB
23 AC 100% 2ms 7888KB
24 AC 100% 4ms 8480KB
25 AC 100% 2ms 8304KB
26 AC 100% 2ms 8400KB
27 AC 100% 4ms 8560KB
28 AC 100% 2ms 8144KB
29 AC 100% 13ms 8464KB
30 AC 100% 3ms 7872KB

ソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

void chmin(int &a,int b) {
	if (a == -1)a = b;
	else if (a > b)a = b;
	return;
}

int n, t[16], a[16][16], dp[1 << 16];


int main() {
	cin >> n;
	rep(i, 0, n)cin >> t[i];
	rep(i, 0, n)rep(j, 0, n)cin >> a[i][j];

	rep(msk, 0, 1 << n)dp[msk] = -1;
	dp[0] = 0;

	rep(msk, 0, 1 << n)rep(u, 0, n)if(!((1<<u)&(msk)) && dp[msk] >= 0){
		int T = t[u];
		rep(j, 0, n)if ((1 << j)&msk)T -= a[j][u];
		chmin(dp[msk+(1<<u)],dp[msk]+T);
	}
	cout << dp[(1<<n)-1] << endl;

	return 0;
}