Submission #241889

#TimeUsernameProblemLanguageResultExecution timeMemory
241889NONAMEVještica (COCI16_vjestica)C++14
32 / 160
374 ms5112 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...