Submission #920173

#	Time	Username	Problem	Language	Result	Execution time	Memory
920173		Whisper	Kronican (COCI16_kronican)	C++17	100 / 100	574 ms	8784 KiB

kronican

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using str = string;
// using T = tuple<double, ll, ll>;

#define int long long
#define Base 31
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for ( int i = b ; i >= a ; i-- )
#define REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i =  n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 31);
constexpr int MAX = 21;
constexpr int Mod = 1e9 + 7;

void setupIO( const string& PROB ){

    //Phu Trong from Nguyen Tat Thanh High School for gifted student

    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen( (PROB + ".inp").c_str(), "r", stdin);
    // freopen( (PROB + ".out").c_str(), "w", stdout);
    cout << fixed << setprecision(10);
}

int c[MAX][MAX];
int f[1 << MAX];
void Whisper(){    
    int n, k; cin >> n >> k;
    FOR(i, 0, n - 1) FOR(j, 0, n - 1) cin >> c[i][j];

    auto get = [&](int x){
        return __builtin_popcount(x);
    };  

    int ans = INF;
    for ( int mask = (1 << n) - 1; mask >= 0 ; mask-- ){
        if (get(mask) < k) continue;
        f[mask] = (mask == (1 << n) - 1 ? 0 : INF );
        for (int i = 0 ; i < n ; i++ ){
            if (mask >> i & 1){
                //đổ thằng j vào i
                for ( int j = 0 ; j < n ; j++ ){
                    if (mask >> j & 1) continue;
                    f[mask] = min(f[mask] , f[mask | (1 << j)] + c[j][i] );
                }
            }
        }
        if (get(mask) == k) ans = min(ans , f[mask]);
    }
    cout << ans;
}               
    
signed main(){
    setupIO("Whisper");
    int Test = 1;
    // cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

• Subtask 1: 100 / 100