Submission #98499

#	Time	Username	Problem	Language	Result	Execution time	Memory
98499		Leonardo_Paes	Kronican (COCI16_kronican)	C++11	100 / 100	1193 ms	4608 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

#define MAXN 21

int mat[MAXN][MAXN];

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

int solve(int x){

    if(dp[x]!=-1)return dp[x];

    if(__builtin_popcount(x)==k)return 0;

    int ans=0x3f3f3f3f;

    for(int i=1; i<=n; i++){
        if(!(x&(1<<(i-1))))continue;
        for(int j=1; j<=n; j++){
            if (i==j or !(x&(1<<(j-1)))) continue;
            int k = x^(1<<(i-1));
            ans=min(ans,mat[i][j] + solve(k));
        }
    }
    return dp[x]=ans;
}

int main(){

    cin >> n >> k;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << solve((1<<n)-1) << endl;
}

• Subtask 1: 100 / 100