# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24989 | samir_droubi | Vještica (COCI16_vjestica) | C++14 | 383 ms | 3180 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;
int n;
int a[17][26];
int s[17];
const int mxn=(1<<17);
int dp[mxn];
int com[mxn];
int calc(int mask)
{
if(dp[mask]!=-1)return dp[mask];
if(mask==0)return 0;
if(__builtin_popcount(mask)==1)
{
int i=0;
for(i;i<n;++i)
if((1<<i)&mask)break;
return s[i];
}
for(int j=0;j<26;++j)
{
int x=(1e9);
for(int i=0;i<n;++i)
if((1<<i)&mask)
x=min(a[i][j],x);
com[mask]+=x;
}
int ans=(1e9);
for(int i=(mask-1)&mask;i>0;i=(i-1)&mask)
ans=min(ans,calc(i)+calc(mask^i)-com[mask]);
return dp[mask]=ans;
}
int main()
{
memset(dp,-1,sizeof dp);
scanf("%d",&n);
for(int i=0;i<n;++i)
{
string t;
cin>>t;
s[i]=t.length();
for(int j=0;j<t.length();++j)
++a[i][t[j]-'a'];
}
printf("%d\n",calc((1<<n)-1));
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |