#include <bits/stdc++.h>
using namespace std;
const int Nmax=22;
const int oo=1e9+7;
int n,k;
int f[Nmax][Nmax];
int dp[(1<<20)+7];
int best[Nmax][(1<<20)+2];
int slv(int bitmask)
{
int res=__builtin_popcount(bitmask);
if (res==k) return 0;
if (dp[bitmask]!=-1) return dp[bitmask];
int cur=1e9;
for (int i=0;i<=n-1;i++)
if ((bitmask&(1<<i))!=0) cur=min(cur,slv(bitmask^(1<<i))+f[i+1][best[i+1][bitmask]]);
return dp[bitmask]=cur;
}
void build_best()
{
for (int bitmask=0;bitmask<=(1<<n);bitmask++)
{
int res=__builtin_popcount(bitmask);
if (res>=k)
{
for (int i=0;i<=n-1;i++)
{
if ((bitmask&(1<<i))!=0)
{
best[i+1][bitmask]=0;
for (int j=0;j<=n-1;j++)
{
if ((bitmask&(1<<j))!=0&&i!=j)
if (f[i+1][j+1]<f[i+1][best[i+1][bitmask]]) best[i+1][bitmask]=j+1;
}
}
}
}
}
}
//void trace(int bitmask)
//{
// int res=__builtin_popcount(bitmask);
// if (res==k)
// {
// cout<<bitmask<<"\n";
// return;
// }
// for (int i=0;i<=n-1;i++)
// if ((bitmask&(1<<i))!=0)
// {
// if (slv(bitmask)==slv(bitmask^(1<<i))+f[i+1][best[i+1][bitmask]]);
// {
// trace(bitmask^(1<<i));
// //break;
// }
// }
//}
int main()
{
//freopen("kronican.inp","r",stdin);
//freopen("kronican.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) cin>>f[i][j];
for (int i=1;i<=n;i++) f[i][0]=oo;
build_best();
memset(dp,-1,sizeof dp);
cout<<slv((1<<n)-1)<<"\n";
// for (int i=1;i<=20;i++)
// {
// for (int j=1;j<=20;j++)
// {
// if (i==j) cout<<0<<" ";
// else cout<<100000<<" ";
// }
// cout<<"\n";
// }
//trace((1<<n)-1);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4472 KB |
Output is correct |
2 |
Correct |
5 ms |
4472 KB |
Output is correct |
3 |
Correct |
5 ms |
4472 KB |
Output is correct |
4 |
Correct |
5 ms |
4600 KB |
Output is correct |
5 |
Correct |
15 ms |
5368 KB |
Output is correct |
6 |
Correct |
29 ms |
6264 KB |
Output is correct |
7 |
Correct |
56 ms |
8056 KB |
Output is correct |
8 |
Correct |
122 ms |
12024 KB |
Output is correct |
9 |
Runtime error |
486 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
10 |
Runtime error |
90 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |