제출 #855902

#제출 시각아이디문제언어결과실행 시간메모리
855902wakandaaaKronican (COCI16_kronican)C++17
100 / 100
696 ms4544 KiB
#include <bits/stdc++.h> #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1 << (x)) #define file "" using namespace std; mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return l + rd() % (r - l + 1); } const int N = 20 + 5; const int mod = 1e9 + 7; // 998244353; const int inf = INT_MAX; const long long llinf = LLONG_MAX; const int LOG = 25; // LOG + 1 template<class T> bool minimize(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool maximize(T &a, T b) { return a < b ? (a = b, true) : false; } template<class T> bool add(T &a, T b) { a += b; while (a > mod) a -= mod; return true; } int n, k; int c[N][N]; int f[bit(20)]; int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen(file".inp", "r",stdin); // freopen(file".out", "w",stdout); cin >> n >> k; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> c[i][j]; memset(f, 0x3f, sizeof f); int ans = f[0]; f[bit(n) - 1] = 0; for (int x = bit(n) - 1; x >= 0; --x) { for (int i = 1; i <= n; ++i) if (getbit(x, i - 1)) { int y = (x ^ bit(i - 1)); int cost = inf; for (int j = 1; j <= n; ++j) if (getbit(y, j - 1)) cost = min(cost, c[i][j]); f[y] = min(f[y], f[x] + cost); } } for (int mask = 1; mask < bit(n); ++mask) { if (__builtin_popcount(mask) <= k) ans = min(ans, f[mask]); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...