제출 #850236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850236		Tai_xiu	Kronican (COCI16_kronican)	C++14	100 / 100	452 ms	5084 KiB

kronican

#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();
}

• Subtask 1: 100 / 100