#include<bits/stdc++.h>
using namespace std;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
long long dp[(1<<16)];
long long c[16][26] = {0};
long long com[(1<<16)];
long long solve(int mask){
if(dp[mask]!=-1)return dp[mask];
if(__builtin_popcount(mask)==1)return 0;
long long ans = 1e18;
for(int s = mask&(mask-1);s;s=s&(s-1)){
ans = min(ans,solve(s)+solve(mask^s)+((-2)*com[mask]+com[s]+com[(mask^s)]));
}
return dp[mask] = ans;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;cin>>n;
for(int i = 0;i<n;i++){
string s;cin>>s;
for(auto j:s){
c[i][j-'a']++;
}
}
memset(dp,-1,sizeof dp);
for(int mask = 0;mask<(1<<n);mask++){
long long ch[26] = {0};
for(int j = 0;j<26;j++)ch[j] = 1e9;
for(int j = 0;j<n;j++){
if(mask&(1<<j)){
for(int k = 0;k<26;k++)ch[k]= min(ch[k],c[j][k]);
}
}
for(int j = 0;j<26;j++){
com[mask]+=ch[j];
}
}
cout<<solve((1<<n)-1)+1+com[(1<<n)-1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
840 KB |
Output isn't correct |
| 4 |
Incorrect |
22 ms |
1276 KB |
Output isn't correct |
| 5 |
Incorrect |
19 ms |
1352 KB |
Output isn't correct |
| 6 |
Incorrect |
19 ms |
1620 KB |
Output isn't correct |
| 7 |
Incorrect |
23 ms |
1760 KB |
Output isn't correct |
| 8 |
Incorrect |
23 ms |
1828 KB |
Output isn't correct |
| 9 |
Incorrect |
21 ms |
1792 KB |
Output isn't correct |
| 10 |
Incorrect |
25 ms |
1852 KB |
Output isn't correct |
