oj.uz

Submission #1016210

# Submission time Handle Problem Language Result Execution time Memory
1016210 2024-07-07T13:58:22 Z VMaksimoski008 Kronican (COCI16_kronican) C++17
100 / 100
 656 ms 4688 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dp[1<<20];
int n, k, mat[20][20];

int f(int mask) {
    if(__builtin_popcount(mask) == k) return 0;
    if(dp[mask] != -1) return dp[mask];

    int ans = 1e8;
    for(int i=0; i<n; i++) {
        if((mask & (1 << i)) == 0) continue;
        for(int j=0; j<n; j++) {
            if(i == j) continue;
            if((mask & (1 << j)) == 0) continue;
            ans = min(ans, f(mask^(1<<i)) + mat[i][j]);
        }
    }

    return dp[mask] = ans;
}

signed main() {
    cin >> n >> k;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) cin >> mat[i][j];
    
    memset(dp, -1, sizeof(dp));
    cout << f( (1 << n) - 1 ) << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 7 ms 4544 KB Output is correct
6 Correct 19 ms 4544 KB Output is correct
7 Correct 28 ms 4444 KB Output is correct
8 Correct 74 ms 4688 KB Output is correct
9 Correct 656 ms 4520 KB Output is correct
10 Correct 60 ms 4444 KB Output is correct