oj.uz

Submission #93189

# Submission time Handle Problem Language Result Execution time Memory
93189 2019-01-07T04:09:42 Z tqhb2502 Kronican (COCI16_kronican) C++
80 / 100
 106 ms 33792 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn=25;
const int oo=1e9+11;

int n, k, e[maxn][maxn], cost[maxn][1<<20], dp[1<<20];

void Try(int i, int minn, int state, int id)
{
    if (i==n+1) { cost[id][state]=minn; return; }
    if (i==id) Try(i+1, minn, state|(1<<(i-1)), id);
    else
    {
        Try(i+1, minn, state, id);
        Try(i+1, min(minn, e[id][i]), state|(1<<(i-1)), id);
    }
}

int slv(int mask)
{
    if (__builtin_popcount(mask)==k) return 0;
    if (dp[mask]!=-1) return dp[mask];
    int cur=oo;
    for (int i=1; i<=20; i++)
    {
        if ((mask&(1<<(i-1)))==0) continue;
        cur=min(cur, slv(mask-(1<<(i-1)))+cost[i][mask]);
    }
    return dp[mask]=cur;
}

int main()
{
    //freopen("KRONICAN.INP", "r", stdin);
    //freopen("KRONICAN.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin>>e[i][j];
    for (int i=1; i<=n; i++) Try(1, oo, 0, i);
    memset(dp, -1, sizeof(dp));
    cout<<slv((1<<n)-1);
    return 0;
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4476 KB Output is correct
2 Correct 5 ms 4472 KB Output is correct
3 Correct 4 ms 4472 KB Output is correct
4 Correct 5 ms 4600 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 11 ms 6264 KB Output is correct
7 Correct 22 ms 8184 KB Output is correct
8 Correct 48 ms 12068 KB Output is correct
9 Runtime error 105 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 106 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)