Submission #850236

#TimeUsernameProblemLanguageResultExecution timeMemory
850236Tai_xiuKronican (COCI16_kronican)C++14
100 / 100
452 ms5084 KiB
#include <bits/stdc++.h> using namespace std; int n,k,dp[1<<20]; int a[20][20]; void solve() { vector<int>lt; fill (dp,dp+(1<<20),1000000000); for (int i=0;i<(1<<n);i++){ if (__builtin_popcount(i)==k) lt.push_back(i); } dp[(1<<n)-1]=0; int premask; for (int mask=(1<<n)-1;mask>=lt[0];mask--){ vector<int>tam,tam1; for (int j=0;j<n;j++){ if (((mask>>j)&1)==0) tam.push_back(j); else tam1.push_back(j); } for (int j:tam){ premask=mask^(1<<j); int mi=1000000000; for (int k:tam1){ mi=min(mi,a[j][k]); dp[mask]=min(dp[mask],dp[premask]+mi); } } } int kq=1000000000; for (int i:lt){ kq=min(kq,dp[i]); } cout<<kq; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>k; for (int i=0;i<n;i++){ for (int j=0;j<n;j++) cin>>a[i][j]; } solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...