# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
489582 | cpp219 | Vještica (COCI16_vjestica) | C++14 | 489 ms | 1364 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>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = (1 << 16) + 1;
const ll inf = 1e9 + 7;
string s;
ll c[N],dp[N],n,cnt[20][30],sz[30];
ll LCP(ll mask){
if (c[mask] != -1) return c[mask];
ll tmp[30]; fill(tmp,tmp + 27,inf);
for (ll i = 0;i < n;i++){
if (((mask >> i) & 1) == 0) continue;
for (ll j = 0;j < 26;j++)
tmp[j] = min(tmp[j],cnt[i][j]);
}
ll ans = 0;
for (ll j = 0;j < 26;j++) ans += tmp[j];
return c[mask] = ans;
}
ll f(ll mask){
if (__builtin_popcount(mask) == 1) return LCP(mask);
ll &res = dp[mask];
if (res != -1) return res;
ll nw = mask; res = inf;
while(nw){
nw = ((nw - 1) & mask);
res = min(res,f(nw) + f(mask ^ nw) - LCP(mask));
}
return res;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n;
for (ll i = 0;i < n;i++){
cin>>s; sz[i] = s.size();
for (ll j = 0;j < s.size();j++) cnt[i][s[j] - 'a']++;
}
memset(dp,-1,sizeof(dp)); memset(c,-1,sizeof(c));
cout<<f((1 << n) - 1) + 1;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |