Submission #238550

#	Time	Username	Problem	Language	Result	Execution time	Memory
238550		marlicu	Kronican (COCI16_kronican)	C++14	30 / 100	1857 ms	65540 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

typedef bitset <20> stanje;
typedef pair <stanje, int> psi;

int n, k;
int napor[25][25];
map <string, int> dp;
queue <string> q;

void izracunaj(string b, int x) {
    string sb = b;
    b[x] = '0';

    int mini = 1e5 + 5;

    //cout << sb << " " << x << " " << dp[sb] << " ";
    int od_prije = max(0, dp[sb]);

    //cout << od_prije << " " << b << " ";

    for (int i = 0; i < n; i++) {
        if (b[i] == '0') continue;
        mini = min(mini, napor[x][i]);
    }

    if (dp[b] != 0) dp[b] =  min(dp[b], od_prije + mini);
    else dp[b] = od_prije + mini;
    //cout << mini << " " << dp[b] << '\n';
    q.push(b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> napor[i][j];
        }
    }

    string sve, nista;
    for (int i = 0; i < n; i++) sve += "1";
    for (int i = 0; i < n; i++) nista += "0";
    q.push(sve);
    dp[sve] = -1;
    dp[nista] = -1;
    int sol = 1e6;

    while (!q.empty()) {
        string t = q.front();
        int koliko = 0;
        for (int i = 0; i < n; i++) {
            if (t[i] == '1') koliko++;
        }

        //cout << "::: " << t << " " << koliko << " " << k << '\n';

        if (koliko > k) {
            for (int i = 0; i < n; i++) {
                if (t[i] == '1') izracunaj(t, i);
            }
        }

        if (koliko == k) sol = min(sol, dp[t]);

        //cout << t << " " << dp[t] << '\n';
        q.pop();
    }

    cout << max(0, sol) << '\n';

    return 0;
}

• Subtask 1: 30 / 100