oj.uz

Submission #241889

# Submission time Handle Problem Language Result Execution time Memory
241889 2020-06-26T09:05:53 Z NONAME Vještica (COCI16_vjestica) C++14
32 / 160
 374 ms 5112 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int oo = 1e9;

int n, dp[(1 << 20)], cnt[20][26];

int calc(int msk) {
    int c[26] {};

    for (int i = 0; i < 26; ++i)
        c[i] = n;

    for (int i = 0; i < n; ++i)
        if ((1 << i) & msk) {
            for (int j = 0; j < 26; ++j)
                c[j] = min(c[j], cnt[i][j]);
        }

    int len = 0;

    for (int i = 0; i < 26; ++i)
        len += c[i];

    return len;
}

int solve(int msk) {
    int &res = dp[msk];
    if (res != -1)
        return res;

    res = oo;

    int pr = calc(msk);

    if (__builtin_popcount(msk) == 1)
        return res = pr;

    for (int i = (msk - 1) & msk; i > 0; i = (i - 1) & msk) {
        int cur = solve(i) + solve(msk ^ i) - pr;
        res = min(res, cur);
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #ifdef _LOCAL
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
    #endif // _LOCAL

    memset(dp, -1, sizeof(dp));
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;

        int m = int(s.size());

        for (int j = 0; j < m; ++j)
            ++cnt[i][s[j] - 'a'];
    }

    cout << solve((1 << n) - 1) + 1;
}

Subtask #1
32.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Incorrect 7 ms 4480 KB Output isn't correct
4 Incorrect 351 ms 4480 KB Output isn't correct
5 Incorrect 353 ms 4600 KB Output isn't correct
6 Incorrect 357 ms 4808 KB Output isn't correct
7 Incorrect 353 ms 5108 KB Output isn't correct
8 Incorrect 357 ms 5112 KB Output isn't correct
9 Incorrect 374 ms 5008 KB Output isn't correct
10 Incorrect 345 ms 4992 KB Output isn't correct