oj.uz

Submission #920173

# Submission time Handle Problem Language Result Execution time Memory
920173 2024-02-02T07:24:50 Z Whisper Kronican (COCI16_kronican) C++17
100 / 100
 574 ms 8784 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 548 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 13 ms 2652 KB Output is correct
7 Correct 26 ms 2640 KB Output is correct
8 Correct 54 ms 2640 KB Output is correct
9 Correct 574 ms 8784 KB Output is correct
10 Correct 86 ms 8528 KB Output is correct