Submission #886748

#	Time	Username	Problem	Language	Result	Execution time	Memory
886748		vjudge1	Kronican (COCI16_kronican)	C++17	100 / 100	548 ms	4432 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;

const int MAXN = 20, MAXB = (1<<20);

int dp[MAXB], c[MAXN][MAXN];

int cnt(int x){
    int c = 0;
    while (x){
        x -= x&-x;
        c++;
    }
    return c;
}

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // cin.setf(ios::fixed);
    // cin.precision(2);


    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

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

    int mb = (1<<n) - 1; // todos os copos ativos
    dp[mb] = 0;

    int an = 1e8;
    if (n<=k){
        cout << 0 << "\n";
        return 0;
    }

    for (int bi = mb-1;bi>0;bi--){
        dp[bi] = 1e8;

        for (int i=0, a = 1;i<n;i++, a = (a<<1)){
            if ((bi&a)) continue; // pra cada bit inativo

            for (int j=0, b = 1;j<n;j++, b = (b << 1)){
                if (!(b&bi)) continue; // pra cada bit ativo

                dp[bi] = min(dp[bi], dp[(bi|a)] + c[i][j]);
            }
        }
        if (cnt(bi) <= k) an = min(an, dp[bi]);
    }

    cout << an << "\n";

    return 0;
}

• Subtask 1: 100 / 100