Submission #630888

#TimeUsernameProblemLanguageResultExecution timeMemory
630888inksamuraiPohlepko (COCI16_pohlepko)C++17
0 / 80
1086 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rng(i,c,n) for(int i=c;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3phCa4T ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e signed main(){ _3phCa4T; int n,k; cin>>n>>k; vec(vi) tbl(n,vi(n)); rep(i,n){ rep(j,n){ cin>>tbl[i][j]; } } const int pun=1<<n; vi dp(pun,1e9); dp[pun-1]=0; per(msk,pun){ rep(i,n){ if(msk>>i&1){ int w=1e9; rep(j,n){ if((msk>>j&1)and(j!=i)){ w=min(w,dp[msk]+tbl[i][j]); } } // print(w); dp[msk^(1<<i)]=min(dp[msk^(1<<i)],w); } } } int res=1e9; rep(msk,pun){ if(__builtin_popcount(msk)<=k){ // print(msk,dp[msk]); res=min(res,dp[msk]); } } print(res); }
#Verdict Execution timeMemoryGrader output
Fetching results...