oj.uz

Submission #656374

# Submission time Handle Problem Language Result Execution time Memory
656374 2022-11-07T06:59:45 Z leeh18 Vještica (COCI16_vjestica) C++17
160 / 160
 486 ms 1108 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 458 ms 596 KB Output is correct
5 Correct 461 ms 596 KB Output is correct
6 Correct 486 ms 852 KB Output is correct
7 Correct 460 ms 976 KB Output is correct
8 Correct 473 ms 1108 KB Output is correct
9 Correct 480 ms 1104 KB Output is correct
10 Correct 458 ms 980 KB Output is correct