Submission #1185190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185190		settop	Kronican (COCI16_kronican)	C++20	80 / 100	89 ms	131072 KiB

kronican

#include<bits/stdc++.h>
 
#define int long long
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
const int MAXN=3e5+10;
const int MAXP=1e2+10;
const ll inf=0X3f3f3f3f3f3f3f3f;
const int infi=INT_MAX;
const ll MOD=1e9+7;
 
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;

int n,k,m[21][21],dp[(1<<20)][21];

int bt(int mask,int q){
	if(dp[mask][q]!=-inf) return dp[mask][q];
	if(q==k) return 0;
	dp[mask][q]=0;
	int b=inf;
	fall(i,0,n-1){
		if(!(mask & (1<<i))) continue;
		fall(j,0,n-1)
			if(i!=j && (mask & (1<<j))) b=min(b,bt(mask^(1<<i),q-1)+m[i][j]);
	}
	return dp[mask][q]=b;
}

int32_t main(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("multimoo.in","r",stdin);
	//freopen("multimoo.out","w",stdout);

	cin>>n>>k;
	fall(i,0,n-1)
		fall(j,0,n-1)
			cin>>m[i][j];
	fall(i,0,(1<<n)-1)
		fall(j,0,n) dp[i][j]=-inf;
	cout<<bt((1<<n)-1,n)<<"\n";
}

• Subtask 1: 80 / 100