Submission #170502

#	Time	Username	Problem	Language	Result	Execution time	Memory
170502		mdn2002	Kronican (COCI16_kronican)	C++14	90 / 100	2053 ms	8696 KiB

kronican

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,k,a[25][25],dp[(1<<21)];
int f(int mask)
{
    int x=mask,num=0;
    while(x)
    {
        num+=x%2;
        x/=2;
    }
    if(n-num<=k)return 0;
    if(dp[mask]!=-1)return dp[mask];
    int mn=1e9;
    for(int i=0;i<n;i++)
    {
        if((mask&(1<<i))==0)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)continue;
                if((mask&(1<<j))==0)
                {
                    mn=min(mn,a[i][j]+f((mask|(1<<i))));
                }
            }
        }
    }
    return dp[mask]=mn;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("lemonade.in","r",stdin);
    //freopen("lemonade.out","w",stdout);
    memset(dp,-1,sizeof dp);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)cin>>a[i][j];
    }
    cout<<f(0);
}

• Subtask 1: 90 / 100