/*
www.youtube.com/YugiHackerChannel
oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn
#define bit(mask,i) ((mask>>i)&1)
using namespace std;
int n;
string s[16];
int cnt[16][26];
int f[1 << 16];
int val(int mask)
{
vector <int> mi(26, 1e9);
f0 (i, n) if (bit(mask, i))
f0 (j, 26) mi[j] = min(mi[j], cnt[i][j]);
return accumulate(mi.begin(), mi.end(), 0);
}
int calc(int mask)
{
int &ans = f[mask];
if (ans != -1) return ans;
int common = val(mask);
if (__builtin_popcount(mask) == 1) return common;
ans = 1e9;
for (int i=(mask - 1) & mask; i; i = (i-1) & mask)
ans = min(ans, calc(i) + calc(mask ^ i) - common);
return ans;
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
f0 (i, n)
{
cin >> s[i];
for (char c:s[i]) cnt[i][c-'a']++;
}
memset(f, -1, sizeof f);
cout << calc((1 << n) - 1) + 1;
}
Compilation message
vjestica.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
34 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
464 KB |
Output is correct |
| 4 |
Correct |
420 ms |
596 KB |
Output is correct |
| 5 |
Correct |
437 ms |
844 KB |
Output is correct |
| 6 |
Correct |
429 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
421 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
416 ms |
1552 KB |
Output is correct |
| 9 |
Correct |
403 ms |
1488 KB |
Output is correct |
| 10 |
Correct |
454 ms |
1508 KB |
Output is correct |
