oj.uz

Submission #98499

# Submission time Handle Problem Language Result Execution time Memory
98499 2019-02-23T19:16:11 Z Leonardo_Paes Kronican (COCI16_kronican) C++11
100 / 100
 1193 ms 4608 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 21

int mat[MAXN][MAXN];

int dp[(1<<20)], n, k;

int solve(int x){

    if(dp[x]!=-1)return dp[x];

    if(__builtin_popcount(x)==k)return 0;

    int ans=0x3f3f3f3f;

    for(int i=1; i<=n; i++){
        if(!(x&(1<<(i-1))))continue;
        for(int j=1; j<=n; j++){
            if (i==j or !(x&(1<<(j-1)))) continue;
            int k = x^(1<<(i-1));
            ans=min(ans,mat[i][j] + solve(k));
        }
    }
    return dp[x]=ans;
}

int main(){

    cin >> n >> k;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << solve((1<<n)-1) << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 6 ms 4480 KB Output is correct
5 Correct 13 ms 4480 KB Output is correct
6 Correct 25 ms 4608 KB Output is correct
7 Correct 44 ms 4480 KB Output is correct
8 Correct 93 ms 4456 KB Output is correct
9 Correct 1193 ms 4480 KB Output is correct
10 Correct 133 ms 4480 KB Output is correct