Submission #1234520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234520		iancunha	Kronican (COCI16_kronican)	C++20	60 / 100	2096 ms	131072 KiB

kronican

#include <bits/stdc++.h>
//#define int int64_t
#define f first
#define s second
#define opt1 ios_base::sync_with_stdio(false)
#define opt2 cin.tie(NULL)
#define optimize opt1; opt2
#define pb push_back
#define sz(v) (int)v.size()
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
typedef pair<ii, ii> i4;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<i3> vi3;
typedef vector<i4> vi4;
const int inf = 1e8;
const int MAX = 300005;
const int mod = 1e9+7;

int N, K, dist[20][20], dp[(1<<20)][20];
int C[20][(1<<20)];

int dpsol (int mask, int k) {
    if (mask == (1 << N)-1) return 0;
    if (dp[mask][k] != 0) return dp[mask][k];
    int res = inf;
    for (int j = 0; j < N; j++) {
        if (mask & (1<<j)) continue;
        res = min(res, dpsol(mask|(1<<j), k)+C[j][mask]);
        if (k > 0)
            res = min(res, dpsol(mask|(1<<j), k-1));
    }
    return dp[mask][k] = res;
}

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];
    for (int i = 0; i < N; i++) {
        for (int mask = 0; mask < (1<<N); mask++) {
            if (mask & (1<<i)) continue; 
            int 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;
        }
    }
    cout << dpsol(0, K) << endl;
    return 0;
}

• Subtask 1: 60 / 100