Submission #884201

#	Time	Username	Problem	Language	Result	Execution time	Memory
884201		vjudge1	Kronican (COCI16_kronican)	C++17	100 / 100	629 ms	4476 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

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


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

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

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

int main(){

    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    cin >> n >> k;

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


    int an = 1e9, mb = 1<<n;
    if (n <= k) an = 0;

    dp[(mb-1)] = 0; // esforço pra ter todos os copos ativos

    for (int r=n-1;r>=k;r--){
        for (int bi = 1; bi<mb;bi++){
            if (cnt(bi) != r) continue;

            dp[bi] = 1e9;

            for (int i=0, a = 1;i<n;i++, a = (a<<1)){

                if ((a&bi)) continue; // pra cada copo nao existente
    
                for (int j=0, b=1;j<n;j++, b = (b<<1)){ // pra cada copo existente
                    if (!(b&bi)) continue;

                    dp[bi] = min(dp[bi], dp[(bi|a)] + e[i][j]);
                    
                }
            }

            if (r == k) an = min(an, dp[bi]);

        }
    }

    cout << an << "\n";

    return 0;
}

• Subtask 1: 100 / 100