oj.uz

Submission #1098272

# Submission time Handle Problem Language Result Execution time Memory
1098272 2024-10-09T08:10:56 Z Ejen Kronican (COCI16_kronican) C++17
100 / 100
 158 ms 8680 KB 
#include <bits/stdc++.h>

#define el "\n"
#define fu(i, a, b) for (int i = a; i <= b; ++i)
#define fd(i, a, b) for (int i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r) (rng);
}
 
ll last(ll msk)     {return msk & (-msk);}
ll pop_cnt(ll msk)  {return __builtin_popcountll(msk);}
ll ctz(ll msk)      {return __builtin_ctzll(msk);}
ll lg(ll msk)       {return 63 - __builtin_clzll(msk);}
 
template<class T1, class T2> bool minimize(T1 &a, T2 b) {
    return a > b ? a = b, 1 : 0;
}
 
template<class T1, class T2> bool maximize(T1 &a, T2 b) {
    return a < b ? a = b, 1 : 0;
}
 
template<class T> void print(T a) {
    for (auto x : a) cout << x << " ";
    cout << el;
}
 
template<class T> void compress(T &a) {
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
}
 
const long long N = 2e1 + 27, mod = 1e9 + 7, inf = 2e18, bl = 320, lim = 1e6 + 27, base = 311;

ll n, k, res = inf;
ll a[N][N], f[mask(20)];

signed main() {
//    freopen("bai3.inp", "r", stdin);
//    freopen("bai3.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    fu(i, 1, n) fu(j, 1, n) cin >> a[i][j];
    fu(d, 1, n) fu(i, 1, n) fu(j, 1, n) minimize(a[i][j], a[i][d] + a[d][j]);
    // cout << el;
    // fu(i, 1, n) {
    //     fu(j, 1, n) cout << a[i][j] << ' ';
    //     cout << el;
    // }
    memset(f, 0x3f, sizeof(f));
    f[mask(n) - 1] = 0;
    fd(msk, mask(n) - 1, 0) {
        if (pop_cnt(msk) <= k) minimize(res, f[msk]);
        for (ll sub = msk; sub > 0; sub -= last(sub)) {
            ll i = ctz(sub);
            for (ll tmp = msk ^ mask(i); tmp > 0; tmp -= last(tmp)) {
                ll j = ctz(tmp);
                // cout << i << ' ' << j << el;
                minimize(f[msk ^ mask(i)], f[msk] + a[i + 1][j + 1]);
            }
        }
        // break;
    }
    cout << res;
    
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 6 ms 8680 KB Output is correct
7 Correct 9 ms 8540 KB Output is correct
8 Correct 17 ms 8540 KB Output is correct
9 Correct 146 ms 8668 KB Output is correct
10 Correct 158 ms 8540 KB Output is correct