Submission #167656

#	Time	Username	Problem	Language	Result	Execution time	Memory
167656		Flying_dragon_02	Vještica (COCI16_vjestica)	C++14	160 / 160	192 ms	1784 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], dp[ ( 1 << 16 ) ], f[ ( 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 ) );
}

#define bp __builtin_popcount

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        t[i] = s;
        for(int j = 0; j < (int)( s.length() ); j++) {
            int c = (int)( s[j] - 'a' );
            cnt[i][c]++;
        }
    }
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int c = 0; c < 26; c++) {
            int mn = inf;
            for(int bt = 0; bt < n; bt++) {
                if( checkBit( mask, bt ) )
                    mn = min( mn, cnt[bt][c] );
            }
            f[ mask ] += mn;
        }
    }
    dp[0] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        int total = 0, cnt1 = 0;
        for(int bt = 0; bt < n; bt++) {
            if( checkBit( mask, bt ) )
                total += (int)( t[bt].length() ), cnt1++;
        }
        cnt1 -= 1;
        total -= cnt1 * f[ mask ];
        dp[ mask ] = total;
        //cout << dp[mask] << " " << total << "\n";
        for(int submask = mask; submask > 0; submask = (submask - 1) & mask ) {
            if( submask == mask ) continue;
            dp[ mask ] = min( dp[mask], dp[ submask ] + dp[ mask ^ submask ] - f[ mask ] );
            //cout << mask << " " << submask << "\n";
        }
    }
    cout << dp[ (1 << n) - 1 ] + 1;
}

• Subtask 1: 160 / 160