#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n;
string s[30];
ll scnt[30][30];
ll bcnt[1<<18];
ll dp[1<<18];
ll func(ll bit){
if(dp[bit] != -1)
return dp[bit];
ll pre = 0;
dp[bit] = 0;
ll use[30][30];
ll left[30];
for(ll i = 0; i < n; ++i){
left[i] = 0;
for(ll j = 0; j <= 'z'-'a'; ++j){
use[i][j] = scnt[i][j];
left[i] += use[i][j];
}
}
ll check = 1;
while(check){
check = 0;
for(ll i = 0; i <= 'z'-'a'; ++i){
ll cur = 1e18;
for(ll j = 0; j < n; ++j)
if((bit&(1<<j)) != 0 && left[j] != 0)
cur = min(cur, use[j][i]);
if(cur == 1e18)
goto HERE;
pre += cur;
for(ll j = 0; j < n; ++j)
if((bit&(1<<j)) != 0 && left[j] != 0){
use[j][i] -= cur;
left[j] -= cur;
if(left[j] == 0)
check = 1;
}
}
}
HERE:;
dp[bit] = pre;
//cout << bit << " " << pre << "\n";
for(ll j = 0; j < n; ++j)
if((bit&(1<<j)) != 0)
dp[bit] += max((ll)0, (ll)s[j].size()-pre);
for(ll bit2 = ((bit-1)&bit); bit2 > 0; bit2 = ((bit2-1)&bit))
dp[bit] = min(dp[bit], func(bit2)+func(bit-bit2));
return dp[bit];
}
ll check(string s1, string s2){
for(int i = 0; i < min(s1.size(), s2.size()); ++i)
if(s1[i] != s2[i])
return 0;
if(s1.size() > s2.size())
return 1;
return 2;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i){
cin >> s[i];
for(auto u : s[i])
scnt[i][u-'a']++;
}
for(ll bit = 0; bit < (1<<n); ++bit){
dp[bit]= -1;
}
cout << 1+func((1<<n)-1) << "\n";
}
Compilation message
vjestica.cpp: In function 'll check(std::__cxx11::string, std::__cxx11::string)':
vjestica.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < min(s1.size(), s2.size()); ++i)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
380 KB |
Output isn't correct |
| 4 |
Incorrect |
424 ms |
1148 KB |
Output isn't correct |
| 5 |
Incorrect |
644 ms |
1144 KB |
Output isn't correct |
| 6 |
Incorrect |
582 ms |
1656 KB |
Output isn't correct |
| 7 |
Incorrect |
580 ms |
1912 KB |
Output isn't correct |
| 8 |
Incorrect |
637 ms |
2040 KB |
Output isn't correct |
| 9 |
Incorrect |
493 ms |
2040 KB |
Output isn't correct |
| 10 |
Incorrect |
755 ms |
2040 KB |
Output isn't correct |
