Submission #1132868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132868		DangKhoizzzz	Kronican (COCI16_kronican)	C++20	100 / 100	699 ms	4552 KiB

kronican

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>


using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;

int n , k , c[30][30], dp[(1 << 21)];

int getbit(int a , int b)
{
    return ((a >> b)&1);
}

int flip(int a , int b)
{
    return (a ^ (1 << b));
}

void solve()
{
    cin >> n >> k;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) cin >> c[i][j];
    }

    for(int i = 0; i < (1 << n) ; i++) dp[i] = INF;

    dp[(1 << n) - 1] = 0;

    for(int mask = (1 << n) - 1; mask >= 0; mask--)
    {
        for(int i = 0; i < n; i++)
        {
            if(getbit(mask , i) == 1)
            {
                int cost = INF;

                for(int j = 0; j < n; j++)
                {
                    if(i != j && getbit(mask , j) == 1)
                    {
                        cost = min(cost , c[i][j]);
                    }
                }

                dp[flip(mask , i)] = min(dp[flip(mask , i)] , dp[mask] + cost);
            }
        }
    }

    int ans = INF;

    for(int mask = 0; mask < (1 << n); mask++)
    {
        if(__builtin_popcount(mask) <= k)
        {
            ans = min(ans , dp[mask]);
        }
    }
    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 100 / 100