Submission #1185185

#TimeUsernameProblemLanguageResultExecution timeMemory
1185185settopKronican (COCI16_kronican)C++20
80 / 100
107 ms131072 KiB
#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[25][25],dp[(1<<21)][25]; bool z[(1<<21)][25]; int bt(int mask,int q){ if(z[mask][q]) return dp[mask][q]; if(q==k) return 0; z[mask][q]=1; 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]; cout<<bt((1<<n)-1,n)<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...