# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
365265 | FatihSolak | Vještica (COCI16_vjestica) | C++17 | 122 ms | 1132 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 N 16
using namespace std;
int n;
int dp[(1<<N)];
int arr[N][26];
int main(){
cin >> n;
for(int i=0;i<n;i++){
string s;
cin >> s;
for(auto u:s){
arr[i][u-'a']++;
}
}
for(int i=1;i<(1<<n);i++){
dp[i] = 1e9;
}
dp[0] = 0;
for(int i=0;i<n;i++){
dp[1<<i] = 0;
for(int j=0;j<26;j++)dp[1<<i]+=arr[i][j];
}
for(int i=1;i<(1<<n);i++){
for(int m = i;m;m=(m-1)&i){
dp[i] = min(dp[i],dp[m]+dp[i-m]);
}
for(int j=0;j<26;j++){
int mini = 1e9;
int cnt =0;
for(int c = 0;c<n;c++){
if((1<<c)&i){
mini = min(mini,arr[c][j]);
cnt++;
}
}
if(cnt != 1)
dp[i] -= mini;
}
}
cout <<dp[(1<<n) - 1] + 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |