oj.uz

Submission #93204

# Submission time Handle Problem Language Result Execution time Memory
93204 2019-01-07T08:44:49 Z annast Kronican (COCI16_kronican) C++14
60 / 100
 2000 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;
int n,k,a[25][25],s,ans;
bool kt[25];
void Try(int i)
{
    if (s>ans) return;
    if (i==k)
    {
        ans=min(s,ans);
        return;
    }
    for (int l=1;l<=n;l++)
        if (kt[l])
    {
        kt[l]=false;
        int MIN=1e9;
        for (int j=1;j<=n;j++)
            if (kt[j] && j!=l) MIN=min(MIN,a[l][j]);
        s+=MIN;
        Try(i-1);
        s-=MIN;
        kt[l]=true;
    }
}
int main()
{
    //freopen("kronican.inp","r",stdin);
    //freopen("kronican.out","w",stdout);
    ios_base::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>>a[i][j];
    memset(kt,true,sizeof(kt));
    s=0;ans=1e9;
    Try(n);
    cout<<ans;
    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 43 ms 376 KB Output is correct
5 Correct 387 ms 376 KB Output is correct
6 Execution timed out 2049 ms 256 KB Time limit exceeded
7 Execution timed out 2067 ms 376 KB Time limit exceeded
8 Execution timed out 2064 ms 256 KB Time limit exceeded
9 Execution timed out 2071 ms 376 KB Time limit exceeded
10 Correct 19 ms 376 KB Output is correct