Submission #1216091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216091		Rafael_Augusto	Kronican (COCI16_kronican)	C++20	100 / 100	946 ms	9680 KiB

kronican

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define f first
#define s second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MASK = (1<<20)+7;
const int MAXN = 20+7;

int n, k;
int dist[MAXN][MAXN];
int dp[MASK];
bool mark[MASK];

int bt(int mask){
    if(mark[mask]) return dp[mask];
    if(__popcount(mask) <= k) return 0;

    mark[mask]=1;

    int mn=1e9;

    fall(i, 0, n){
        if(((1<<i)&mask) == 0) continue;

        fall(j, 0, n) if(((1<<j)&mask) && i != j) mn = min(mn, bt(mask^(1<<i))+dist[i][j]);
    }

    return dp[mask]=mn;
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;

    fall(i, 0, n)
    fall(j, 0, n) cin >> dist[i][j];

    cout << bt((1<<n)-1) << "\n";
}

• Subtask 1: 100 / 100