oj.uz

Submission #238550

# Submission time Handle Problem Language Result Execution time Memory
238550 2020-06-11T18:51:39 Z marlicu Kronican (COCI16_kronican) C++14
30 / 100
 1857 ms 65540 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 57 ms 2296 KB Output is correct
4 Runtime error 1694 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1857 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1851 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 1100 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1115 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 1185 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 1188 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)