Submission #1235508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235508		iancunha	Kronican (COCI16_kronican)	C++20	80 / 100	108 ms	131072 KiB

kronican

#include <bits/stdc++.h>
#define opt1 ios_base::sync_with_stdio(false)
#define opt2 cin.tie(NULL)
#define optimize opt1; opt2
using namespace std;
const int inf = 1e8;
const int MAX = 300005;
const int mod = 1e9+7;

int N, K, dist[20][20];

int32_t main () {
	  optimize;
    cin >> N >> K;
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> dist[i][j];
    
    int res, C[N][(1<<N)], dp[(1<<N)][N];
    
    for (int i = 0; i < N; i++) {
        for (int mask = 0; mask < (1<<N)-1; mask++) {
            if (mask & (1<<i)) continue; 
            res = inf;
            for (int j = 0; j < N; j++) {
                if (mask & (1<<j) || i == j) continue;
                res = min(res, dist[i][j]);
            }
            C[i][mask] = res;
        }
    }
    
    for (int k = 0; k <= K; k++)
        dp[(1<<N)-1][k] = 0;  
    
    for (int mask = (1<<N)-2; mask >= 0; mask--) {
        for (int k = 0; k <= K; k++) {
            res = inf;
            for (int j = 0; j < N; j++) {
                if (mask & (1<<j)) continue;
                res = min(res, dp[mask|(1<<j)][k]+C[j][mask]);
                if (k > 0)
                    res = min(res, dp[mask|(1<<j)][k-1]);
            }
            dp[mask][k] = res;
        }
    }
    
    cout << dp[0][K] << endl;
    return 0;
}

• Subtask 1: 80 / 100