# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
241890 | NONAME | Vještica (COCI16_vjestica) | C++14 | 205 ms | 8824 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll oo = 1e18;
ll n, dp[(1 << 20)], cnt[20][26];
ll calc(ll msk) {
ll c[26] {};
for (ll i = 0; i < 26; ++i)
c[i] = n;
for (ll i = 0; i < n; ++i)
if ((1 << i) & msk) {
for (ll j = 0; j < 26; ++j)
c[j] = min(c[j], cnt[i][j]);
}
ll len = 0;
for (ll i = 0; i < 26; ++i)
len += c[i];
return len;
}
ll solve(ll msk) {
ll &res = dp[msk];
if (res != -1)
return res;
res = oo;
ll pr = calc(msk);
if (__builtin_popcount(msk) == 1)
return res = pr;
for (ll i = (msk - 1) & msk; i > 0; i = (i - 1) & msk) {
ll 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 (ll i = 0; i < n; ++i) {
string s;
cin >> s;
ll m = ll(s.size());
for (ll j = 0; j < m; ++j)
++cnt[i][s[j] - 'a'];
}
cout << solve((1 << n) - 1) + 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |