#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
const int mn = 21, inf = 1e18;
int n, k, a[mn][mn];
int dp[mn][(1 << 19) + 1];
void solve(){
cin >> n >> k;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
fill(&dp[0][0], &dp[0][0] + mn * ((1 << 19) + 1), inf);
for(int mask = 0; mask < (1 << n); mask++){
vector <int> cand;
for(int i = 0; i < n; i++){
if(mask & (1 << i)) cand.push_back(i);
}
dp[1][mask] = INT_MAX;
for(auto i : cand){
int val = 0;
for(auto j : cand){
val += a[i][j];
}
dp[1][mask] = min(dp[1][mask], val);
}
}
dp[1][0] = 0;
for(int i = 2; i <= k; i++){
for(int mask = 0; mask < (1 << n); mask++){
dp[i][mask] = dp[i - 1][mask];
for(int sub = mask; sub; sub = (sub - 1) & mask){
dp[i][mask] = min(dp[i - 1][sub] + dp[1][mask - sub], dp[i][mask]);
}
}
}
cout << dp[k][(1 << n) - 1];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
kronican.cpp:6:26: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
6 | const int mn = 21, inf = 1e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |