Submission #1182522

#TimeUsernameProblemLanguageResultExecution timeMemory
1182522nagornzKronican (COCI16_kronican)C++20
100 / 100
386 ms8648 KiB
#include <bits/stdc++.h> #define int long long #define double long double #define pii pair <int,int> #define tiii tuple <int, int, int> #define f first #define s second #define all(x) x.begin(), x.end() #define ub(a, b) upper_bound(a.begin(), a.end(), b) - a.begin() #define lb(a, b) lower_bound(a.begin(), a.end(), b) - a.begin() #define ve vector #define graph(a, n) vector <int> a[n]; #define wgraph(a, n) vector <pii> a[n]; #define emb emplace_back #define em emplace #define ins insert #define er erase #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) using namespace std; template <typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>; const int mod = 1e9 + 7; const int inf = 1e18; const int N = 20; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int n, k, a[N][N], dp[1 << N]; int32_t main(){ iShowSpeed; cin >> n >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } for (auto &e : dp) e = inf; dp[(1 << n) - 1] = 0; int ans = inf; for (int i = (1 << n) - 1; i >= 0; i--) { if (__builtin_popcount(i) == k) ans = min(ans, dp[i]); for (int u = 0; u < n; u++) { if (!(i & (1 << u))) continue; for (int v = 0; v < n; v++) { if (u == v) continue; int mask = i; mask ^= (1 << u); mask |= (1 << v); dp[mask] = min(dp[mask], dp[i] + a[u][v]); } } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...