oj.uz

Submission #170503

# Submission time Handle Problem Language Result Execution time Memory
170503 2019-12-25T14:10:14 Z mdn2002 Kronican (COCI16_kronican) C++14
100 / 100
 1374 ms 8592 KB 
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,k,a[25][25],dp[(1<<21)];
int f(int mask,int num)
{
    if(n-num<=k)return 0;
    if(dp[mask]!=-1)return dp[mask];
    int mn=1e9;
    for(int i=0;i<n;i++)
    {
        if((mask&(1<<i))==0)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)continue;
                if((mask&(1<<j))==0)
                {
                    mn=min(mn,a[i][j]+f((mask|(1<<i)),num+1));
                }
            }
        }
    }
    return dp[mask]=mn;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("lemonade.in","r",stdin);
    //freopen("lemonade.out","w",stdout);
    memset(dp,-1,sizeof dp);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)cin>>a[i][j];
    }
    cout<<f(0,0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 9 ms 8568 KB Output is correct
3 Correct 9 ms 8572 KB Output is correct
4 Correct 9 ms 8572 KB Output is correct
5 Correct 19 ms 8572 KB Output is correct
6 Correct 33 ms 8568 KB Output is correct
7 Correct 57 ms 8568 KB Output is correct
8 Correct 120 ms 8568 KB Output is correct
9 Correct 1374 ms 8592 KB Output is correct
10 Correct 127 ms 8568 KB Output is correct