# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1021295 | ZeroCool | Kronican (COCI16_kronican) | C++14 | 562 ms | 8640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define int long long
const int N = 20;
const int INF = 1e17;
const int X = 1e5 + 20;
#pragma GCC optimize("unroll-loops,O2,Ofast,O3")
#pragma GCC target("avx2")
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
int n, k;
cin>>n>>k;
int A[n][n];
for(int i =0; i < n;i++){
for(int j = 0;j < n;j++){
cin>>A[i][j];
}
}
int dp[(1 << n)];
for(int i = 0;i < (1 << n);i++)dp[i] = INF;
dp[(1 << n) - 1] = 0;
int ans = INF;
for(int msk = (1 << n) - 1;msk >= 0;msk--){
if(__builtin_popcount(msk) <= k){
ans = min(ans, dp[msk]);
continue;
}
for(int j = 0;j < n;j++){
if((1 << j) & msk){
for(int k = 0;k < n;k++){
if(j == k)continue;
if((1 << k) & msk){
dp[msk ^ (1 << j)] = min(dp[msk ^ (1 << j)], dp[msk] + A[j][k]);
}
}
}
}
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |