oj.uz

Submission #170502

# Submission time Handle Problem Language Result Execution time Memory
170502 2019-12-25T14:07:51 Z mdn2002 Kronican (COCI16_kronican) C++14
90 / 100
 2000 ms 8696 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 x=mask,num=0;
    while(x)
    {
        num+=x%2;
        x/=2;
    }
    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))));
                }
            }
        }
    }
    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);
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8696 KB Output is correct
2 Correct 9 ms 8568 KB Output is correct
3 Correct 9 ms 8568 KB Output is correct
4 Correct 9 ms 8568 KB Output is correct
5 Correct 33 ms 8568 KB Output is correct
6 Correct 72 ms 8696 KB Output is correct
7 Correct 141 ms 8588 KB Output is correct
8 Correct 330 ms 8668 KB Output is correct
9 Execution timed out 2053 ms 8568 KB Time limit exceeded
10 Correct 460 ms 8568 KB Output is correct