Submission #656374

#	Time	Username	Problem	Language	Result	Execution time	Memory
656374		leeh18	Vještica (COCI16_vjestica)	C++17	160 / 160	486 ms	1108 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N;
    vector<array<int, 26>> g(N);
    for (auto i = 0; i < N; ++i) {
        fill(g[i].begin(), g[i].end(), 0);
        string s;
        cin >> s;
        for (auto c : s) {
            ++g[i][c - 'a'];
        }
    }
    vector<int> dp(1 << N, -1);
    constexpr auto inf = (int)1e9;
    auto pre = [&](auto mask) {
        array<int, 26> cnt;
        fill(cnt.begin(), cnt.end(), inf);
        for (auto i = 0; i < N; ++i) {
            if (mask >> i & 1) {
                for (auto j = 0; j < 26; ++j) {
                    cnt[j] = min(cnt[j], g[i][j]);
                }
            }
        }
        auto ret = 0;
        for (auto x : cnt) {
            if (x < inf) {
                ret += x;
            }
        }
        return ret;
    };
    auto f = [&](auto self, int mask) -> int {
        assert(mask);
        auto &ret = dp[mask];
        if (~ret) return ret;
        if (__builtin_popcount(mask) == 1) {
            auto i = __builtin_ctz(mask);
            ret = accumulate(g[i].begin(), g[i].end(), 0);
            return ret;
        }
        ret = inf;
        auto p = pre(mask);
        for (auto i = (mask - 1) & mask; i > 0; i = (i - 1) & mask) {
            ret = min(ret, self(self, i) + self(self, mask ^ i) - p);
        }
        return ret;
    };
    auto ans = f(f, (1 << N) - 1) + 1;
    cout << ans;
}

• Subtask 1: 160 / 160