oj.uz

Submission #243431

# Submission time Handle Problem Language Result Execution time Memory
243431 2020-07-01T06:36:58 Z VEGAnn Kronican (COCI16_kronican) C++14
100 / 100
 746 ms 4576 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 20;
const int oo = 2e9;
int a[N][N], ans = oo, n, k, f[(1 << N)];

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

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

    fill(f, f + (1 << n), oo);

    f[(1 << n) - 1] = 0;

    for (int msk = (1 << n) - 1; msk > 0; msk--)
        if (__builtin_popcount(msk) <= k){
            ans = min(ans, f[msk]);
        } else {
            for (int fr = 0; fr < n; fr++)
                if (msk & (1 << fr)){
                    int nw = (msk ^ (1 << fr));

                    for (int wh = 0; wh < n; wh++)
                        if (nw & (1 << wh))
                            f[nw] = min(f[nw], f[msk] + a[fr][wh]);
                }
        }

    cout << ans;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 19 ms 512 KB Output is correct
7 Correct 34 ms 640 KB Output is correct
8 Correct 70 ms 896 KB Output is correct
9 Correct 746 ms 4576 KB Output is correct
10 Correct 65 ms 4480 KB Output is correct