제출 #379936

#제출 시각아이디문제언어결과실행 시간메모리
379936vishesh312Kronican (COCI16_kronican)C++17
100 / 100
1160 ms4460 KiB
#include "bits/stdc++.h" using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; */ #define all(x) begin(x), end(x) #define sz(x) (int)x.size() using ll = long long; const int mod = 1e9+7; vector<int> dp; vector<vector<int>> v; int n, k; int rec(int mask) { if (__builtin_popcount(mask) == n) { return dp[mask] = 0; } if (dp[mask] != -1) { return dp[mask]; } dp[mask] = 1e9; for (int i = 0; i < n; ++i) { if (!(mask&(1<<i))) { for (int j = 0; j < n; ++j) { if (mask&(1<<j)) { dp[mask] = min(dp[mask], rec(mask|(1<<i)) + v[i][j]); } } } } return dp[mask]; } void solve(int tc) { cin >> n >> k; dp.resize(1<<n, -1); v.resize(n); for (auto &x : v) { x.resize(n); for (auto &y : x) cin >> y; } int ans = 1e9; for (int mask = 0; mask < (1<<n); ++mask) { if (__builtin_popcount(mask) == k) { ans = min(ans, rec(mask)); } } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...