Submission #446233

#	Time	Username	Problem	Language	Result	Execution time	Memory
446233		zxcvbnm	Vještica (COCI16_vjestica)	C++14	160 / 160	503 ms	1800 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<string> a;
const int maxN = 17;
int dp[(1<<maxN)];
int cnt[maxN][26];

int check(int mask) {
    vector<int> curr(26, INT_MAX);
    for(int i = 0; i < maxN; i++) {
        if (mask & (1 << i)) {
            for(int j = 0; j < 26; j++) {
                curr[j] = min(curr[j], cnt[i][j]);
            }
        }
    }

    int len = 0;
    for(int i : curr) {
        assert(i != INT_MAX);
        len += i;
    }
    return len;
}

int go(int mask) {
    int& ret = dp[mask];
    if (ret != -1) {
        return ret;
    }
    if (mask == 0) {
        return ret = 0;
    }

    int common = check(mask);
    if (__builtin_popcount(mask) == 1) {
        return ret = common;
    }

    ret = INT_MAX;

    for(int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        if (sub == 0 || (sub ^ mask) == 0 || sub == mask || (sub ^ mask) == 0) continue;
        ret = min(ret, go(sub) + go(mask ^ sub) - common);
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    a.resize(n);
    for(auto& i : a) {
        cin >> i;
    }
    memset(dp, -1, sizeof dp);
    memset(cnt, 0, sizeof cnt);

    for(int i = 0; i < n; i++) {
        for(char c : a[i]) {
            cnt[i][c-'a']++;
        }
    }

    cout << go((1<<n)-1)+1 << "\n";
    return 0;
}

• Subtask 1: 160 / 160