oj.uz

Submission #886748

# Submission time Handle Problem Language Result Execution time Memory
886748 2023-12-12T19:53:46 Z vjudge1 Kronican (COCI16_kronican) C++17
100 / 100
 548 ms 4432 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 11 ms 348 KB Output is correct
7 Correct 25 ms 2628 KB Output is correct
8 Correct 53 ms 2676 KB Output is correct
9 Correct 520 ms 4356 KB Output is correct
10 Correct 548 ms 4432 KB Output is correct