結果

提出番号 2144
提出者 ok
言語 C++
提出日時 2018-08-04 19:16:47
問題名 (70)アルゴリズムのお勉強
結果 TLE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 7808KB
2 AC 100% 1ms 8656KB
3 AC 100% 2ms 8400KB
4 AC 100% 2ms 8336KB
5 AC 100% 2ms 8304KB
6 AC 100% 5ms 7952KB
7 AC 100% 2ms 8416KB
8 AC 100% 2ms 8448KB
9 AC 100% 2ms 7776KB
10 AC 100% 2ms 7504KB
11 AC 100% 379ms 8432KB
12 AC 100% 38ms 8400KB
13 AC 100% 399ms 8192KB
14 AC 100% 38ms 7968KB
15 AC 100% 40ms 8432KB
16 AC 100% 2ms 7760KB
17 AC 100% 2ms 7792KB
18 AC 100% 2ms 8368KB
19 TLE 0% 4704ms 8432KB
20 TLE 0% 4719ms 8432KB
21 AC 100% 2ms 8672KB
22 TLE 0% 20001ms 0KB
23 AC 100% 5ms 8352KB
24 TLE 0% 20002ms 0KB
25 TLE 0% 4418ms 8240KB
26 TLE 0% 20002ms 0KB
27 TLE 0% 20001ms 0KB
28 TLE 0% 4419ms 8048KB
29 TLE 0% 20001ms 0KB
30 TLE 0% 20001ms 0KB

ソースコード

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

int N, a[20][20];

int foo(int te[], int x){
	if(x > N-1)return 0;
	int ans = 0, te2[20] = {}, te3[20]={}, co=0;
	for(int i = 0; i < N; i++){
		te2[i]=te[i];
		if(te[i]==1)te3[co++] = i;
	}
	for(int i = 0; i < N; i++){
		if(te[i]==1)continue;
		int ma = 0;
		for(int j = 0; j < co; j++)
			ma+=a[te3[j]][i];
		te2[i]=1;
		ans = max(foo(te2, x+1)+ma, ans);
		te2[i]=0;
	}
	return ans;
}
int main(){	
	int te[20] = {}, sum=0;
	cin>>N;
	for(int i = 0, t; i < N; i++,sum+=t)cin>>t;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			cin>>a[i][j];
	cout<<sum - foo(te, 0)<<endl;
	return 0;
}