Submission #168680

#TimeUsernameProblemLanguageResultExecution timeMemory
168680dolphingarlicVještica (COCI16_vjestica)C++14
0 / 160
2077 ms1016 KiB
/* COCI 2016 Vjestica - Firstly, notice that N is very small. This implies that we should use a bitmask - For each mask, we split the active words into 2 groups and solve recursively for those - solve(mask) = min(solve(A) + solve(B)) where A + B = mask, A & mask == A, B & mask == B, and A & B == 0 - Complexity: O(N log N * 2^N) */ #include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; int n; map<char, int> cnt[16]; int solve(int mask) { int ans = INT_MAX, common = 0; if (!mask) return 0; // cout << mask << ": "; map<char, int> diff; for (char i = 'a'; i <= 'z'; i++) { diff[i] = INT_MAX; FOR(j, 0, n) if (mask & (1 << j)) diff[i] = min(diff[i], cnt[j][i]); common += diff[i]; } FOR(i, 0, n) { if (mask & (1 << i)) { if (diff == cnt[i]) mask -= (1<<i); else for (char j = 'a'; j <= 'z'; j++) cnt[i][j] -= diff[j]; } } // cout << mask << ' ' << common << '\n'; if (!mask) return common; FOR(i, (common == 0), mask) { if ((mask & i) == i) ans = min(ans, solve(i) + solve(mask - i)); } FOR(i, 0, n) { if (mask & (1 << i)) { for (char j = 'a'; j <= 'z'; j++) cnt[i][j] += diff[j]; } } return ans + common; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; FOR(i, 0, n) { for (char j = 'a'; j <= 'z'; j++) cnt[i][j] = 0; string s; cin >> s; for (char j : s) cnt[i][j]++; } cout << solve((1 << n) - 1) + 1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...