Submission #93189

#	Time	Username	Problem	Language	Result	Execution time	Memory
93189		tqhb2502	Kronican (COCI16_kronican)	C++98	80 / 100	106 ms	33792 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

const int maxn=25;
const int oo=1e9+11;

int n, k, e[maxn][maxn], cost[maxn][1<<20], dp[1<<20];

void Try(int i, int minn, int state, int id)
{
    if (i==n+1) { cost[id][state]=minn; return; }
    if (i==id) Try(i+1, minn, state|(1<<(i-1)), id);
    else
    {
        Try(i+1, minn, state, id);
        Try(i+1, min(minn, e[id][i]), state|(1<<(i-1)), id);
    }
}

int slv(int mask)
{
    if (__builtin_popcount(mask)==k) return 0;
    if (dp[mask]!=-1) return dp[mask];
    int cur=oo;
    for (int i=1; i<=20; i++)
    {
        if ((mask&(1<<(i-1)))==0) continue;
        cur=min(cur, slv(mask-(1<<(i-1)))+cost[i][mask]);
    }
    return dp[mask]=cur;
}

int main()
{
    //freopen("KRONICAN.INP", "r", stdin);
    //freopen("KRONICAN.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin>>e[i][j];
    for (int i=1; i<=n; i++) Try(1, oo, 0, i);
    memset(dp, -1, sizeof(dp));
    cout<<slv((1<<n)-1);
    return 0;
}

• Subtask 1: 80 / 100