Submission #167650

#	Time	Username	Problem	Language	Result	Execution time	Memory
167650		Flying_dragon_02	Vještica (COCI16_vjestica)	C++14	0 / 160	37 ms	1144 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair< int, int > ii;

const int inf = 1e8;

int n, cnt[17][27], lmao[17][17], total, dp[( 1 << 16 )];

string t[17];

bool checkBit(int mask, int bit) {
    if( ( mask & ( 1 << bit ) ))
        return 1;
    else
        return 0;
}

int changeBit(int mask, int bit) {
    return ( mask ^ ( 1 << bit ) );
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        t[i - 1] = s;
        for(int j = 0; j < (int)( s.length() ); j++) {
            int c = (int)( s[j] - 'a' );
            cnt[i][c]++;
        }
        total += (int)( s.length() );
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int sum = 0;
            for(int k = 0; k <= 25; k++)
                sum += min( cnt[i][k], cnt[j][k] );
            lmao[i - 1][j - 1] = lmao[j - 1][i - 1] = sum;
        }
    }
    for(int mask = 0; mask < (1 << n); mask++)
        dp[ mask ] = inf;
    for(int i = 0; i < n; i++)
        dp[ ( 1 << i ) ] = (int)( t[i].length() );
    for(int mask = 0; mask < (1 << n); mask++) {
        if( dp[mask] == inf ) continue;
        for(int bt1 = 0; bt1 < n; bt1++) {
            if( !checkBit( mask, bt1 ) ) continue;
            for(int bt2 = 0; bt2 < n; bt2++) {
                if( checkBit( mask, bt2 ) ) continue;
                dp[ changeBit( mask, bt2 ) ] = min( dp[ changeBit( mask, bt2 ) ], dp[ mask ] + (int)( t[bt2].length() ) - lmao[bt1][bt2] );
            }
        }
    }
    cout << dp[ (1 << n) - 1 ] + 1;
}

• Subtask 1: 0 / 160