Submission #93182

# Submission time Handle Problem Language Result Execution time Memory
93182 2019-01-07T03:43:28 Z lalakep Kronican (COCI16_kronican) C++14
80 / 100
486 ms 33792 KB
#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)