oj.uz

Submission #446233

# Submission time Handle Problem Language Result Execution time Memory
446233 2021-07-21T10:20:02 Z zxcvbnm Vještica (COCI16_vjestica) C++14
160 / 160
 503 ms 1800 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 449 ms 844 KB Output is correct
5 Correct 451 ms 976 KB Output is correct
6 Correct 458 ms 1376 KB Output is correct
7 Correct 456 ms 1676 KB Output is correct
8 Correct 460 ms 1800 KB Output is correct
9 Correct 461 ms 1740 KB Output is correct
10 Correct 503 ms 1740 KB Output is correct