oj.uz

Submission #884201

# Submission time Handle Problem Language Result Execution time Memory
884201 2023-12-06T17:58:28 Z vjudge1 Kronican (COCI16_kronican) C++17
100 / 100
 629 ms 4476 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 13 ms 348 KB Output is correct
7 Correct 25 ms 2652 KB Output is correct
8 Correct 56 ms 2652 KB Output is correct
9 Correct 629 ms 4476 KB Output is correct
10 Correct 90 ms 4372 KB Output is correct