oj.uz

답안 #93186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93186 2019-01-07T03:55:58 Z lalakep Kronican (COCI16_kronican) C++14
0 / 100
 924 ms 4500 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)
            {
                int csmin=0;
                for (int j=0;j<=n-1;j++)
                {
                    if ((bitmask&(1<<j))!=0&&j!=i)
                        if (f[i+1][j+1]<f[i+1][csmin]) csmin=j+1;
                }
                cur=min(cur,slv(bitmask^(1<<i))+f[i+1][csmin+1]);
            }
    }
    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;
//                    }
//                }
//            }
//        }
//    }
//}
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";
    return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4400 KB Output isn't correct
2 Incorrect 5 ms 4472 KB Output isn't correct
3 Incorrect 5 ms 4472 KB Output isn't correct
4 Incorrect 5 ms 4472 KB Output isn't correct
5 Incorrect 11 ms 4472 KB Output isn't correct
6 Incorrect 19 ms 4472 KB Output isn't correct
7 Incorrect 33 ms 4472 KB Output isn't correct
8 Incorrect 71 ms 4472 KB Output isn't correct
9 Incorrect 924 ms 4472 KB Output isn't correct
10 Incorrect 66 ms 4500 KB Output isn't correct