Submission #479440

#TimeUsernameProblemLanguageResultExecution timeMemory
479440HabitusVještica (COCI16_vjestica)C++14
0 / 160
2096 ms332 KiB
#include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define dec(x, y) fixed << setprecision((y)) << (x) #define xx first #define yy second #define srt(v) sort((v).begin(), (v).end()) #define srtr(v) sort((v).rbegin(), (v).rend()) #define pb push_back #define popb pop_back #define sz(a) (int)(a).size() #define len(a) (int)(a).length() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n; int s[16][26]; ll dp(int mask) { if(__builtin_popcount(mask)==1) { int l=log2(mask); ll duz=0LL; for(int i=0; i<26; ++i) { duz+=s[l][i]; } return duz; } int p[26]; for(int i=0; i<26; ++i) p[i]=2000000; for(int i=0; i<n; ++i) { if((1<<i)&mask) { for(int j=0; j<26; ++j) { p[j]=min(p[j], s[i][j]); } } } ll duz=0LL; for(int i=0; i<26; ++i) duz+=(ll)p[i]; ll mini=2000000000000000LL; for(int sub=(mask-1)&mask; sub>0; sub=(sub-1)&mask) { if(__builtin_popcount(sub)<__builtin_popcount(mask^sub)) continue; mini=min(mini, dp(sub)+dp(mask^sub)); } return mini-duz; } int main() { ios; cin >> n; for(int i=0; i<n; ++i) { string t; cin >> t; for(int j=0; j<len(t); ++j) { ++s[i][t[j]-'a']; } } cout << dp((1<<n)-1)+1LL; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...