Submission #299008

#TimeUsernameProblemLanguageResultExecution timeMemory
299008jovan_bVještica (COCI16_vjestica)C++17
160 / 160
184 ms1912 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll cnt[25][26]; ll dp[1000005]; ll cc[26]; const int INF = 1000000009; string s[20]; int main(){ ios_base::sync_with_stdio(false); int n; cin >> n; for(int i=1; i<(1<<n); i++) dp[i] = INF; for(int i=1; i<=n; i++){ cin >> s[i]; for(auto c : s[i]){ cnt[i][c-'a']++; } dp[(1<<(i-1))] = s[i].size(); } for(int mask=1; mask<(1<<n); mask++){ int mxpref = 0; for(int i=0; i<26; i++) cc[i] = INF; for(int i=1; i<=n; i++){ if((1<<(i-1)) & mask){ for(int j=0; j<26; j++) cc[j] = min(cc[j], cnt[i][j]); } } for(int i=0; i<26; i++) mxpref += cc[i]; for(int j=mask; j; j=(j-1)&mask){ if(j == mask) continue; dp[mask] = min(dp[mask], -mxpref + dp[j] + dp[j^mask]); } } cout << dp[(1<<n)-1]+1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...