#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC optimization ("O3")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = ll(1e9) + 7, maxn = 1e5 + 5, maxg = 15, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int a[maxn], lst[maxg], cnt[maxg];
vector<int> pos[maxg];
ll cnt_prf[maxn][maxg], cnt_suf[maxn][maxg];
ll dp[1<<maxg];
int main(){
cin.tie(0) -> sync_with_stdio(0);
string s; cin >> s;
int n = sz(s);
rep(i,0,n) a[i] = s[i]-'A', pos[a[i]].pb(i);
rep(i,0,maxg) lst[i] = -1;
rep(i,0,n){
rep(j,0,maxg){
cnt_prf[i][j] = (lst[a[i]] == -1? 0: cnt_prf[lst[a[i]]][j]) + cnt[j];
}
lst[a[i]] = i, cnt[a[i]]++;
}
rep(i,0,maxg) lst[i] = n, cnt[i] = 0;
per(i,n-1,0){
rep(j,0,maxg){
cnt_suf[i][j] = (lst[a[i]] == n? 0: cnt_suf[lst[a[i]]][j]) + cnt[j];
}
lst[a[i]] = i, cnt[a[i]]++;
}
rep(i,0,n) rep(j,0,maxg) cnt_prf[i][j] <<= 1ll, cnt_suf[i][j] <<= 1ll;
rep(msk,1,1<<maxg){
vector<int> bt;
rep(j,0,maxg) if(msk>>j&1) bt.pb(j);
dp[msk] = inf;
for(int c: bt){
if(cnt[c] == 0){
dp[msk] = dp[msk^(1<<c)];
break;
}
auto calc = [&](ll x){
ll res = x*(x-1)/2ll + (cnt[c]-x)*(cnt[c]-x-1)/2ll;
for(int r: bt) if(r - c){
if(x > 0 && x <= cnt[c]) res += cnt_prf[pos[c][x-1]][r];
if(x < cnt[c] && x >= 0) res += cnt_suf[pos[c][x]][r];
}
return res;
};
rep(i,0,cnt[c]+1){
dp[msk] = min(dp[msk], dp[msk^(1<<c)] + calc(i));
}
// int lx = 0, rx = cnt[c]+1;
// while(lx + 1 < rx){
// int mid = (lx + rx)>>1;
// ll l = calc(mid), r = calc(mid+1);
// if(l >= r) lx = mid+1;
// else rx = mid;
// }
//
// dp[msk] = min(dp[msk], dp[msk^(1<<c)] + min(calc(lx), calc(rx)));
}
}
cout << dp[(1<<maxg)-1]/2ll;
if(dp[(1<<maxg)-1]&1ll) cout << ".5";
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
712 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
596 KB |
Output is correct |
4 |
Correct |
8 ms |
596 KB |
Output is correct |
5 |
Correct |
300 ms |
856 KB |
Output is correct |
6 |
Execution timed out |
2081 ms |
20004 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
596 KB |
Output is correct |
2 |
Correct |
17 ms |
516 KB |
Output is correct |
3 |
Correct |
43 ms |
592 KB |
Output is correct |
4 |
Correct |
47 ms |
580 KB |
Output is correct |
5 |
Correct |
39 ms |
596 KB |
Output is correct |
6 |
Correct |
12 ms |
596 KB |
Output is correct |
7 |
Correct |
37 ms |
480 KB |
Output is correct |
8 |
Correct |
12 ms |
568 KB |
Output is correct |
9 |
Correct |
18 ms |
596 KB |
Output is correct |
10 |
Correct |
19 ms |
536 KB |
Output is correct |
11 |
Correct |
19 ms |
484 KB |
Output is correct |
12 |
Correct |
19 ms |
548 KB |
Output is correct |
13 |
Correct |
18 ms |
524 KB |
Output is correct |
14 |
Correct |
19 ms |
596 KB |
Output is correct |
15 |
Correct |
19 ms |
504 KB |
Output is correct |
16 |
Correct |
18 ms |
596 KB |
Output is correct |
17 |
Correct |
19 ms |
564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
596 KB |
Output is correct |
2 |
Correct |
17 ms |
516 KB |
Output is correct |
3 |
Correct |
43 ms |
592 KB |
Output is correct |
4 |
Correct |
47 ms |
580 KB |
Output is correct |
5 |
Correct |
39 ms |
596 KB |
Output is correct |
6 |
Correct |
12 ms |
596 KB |
Output is correct |
7 |
Correct |
37 ms |
480 KB |
Output is correct |
8 |
Correct |
12 ms |
568 KB |
Output is correct |
9 |
Correct |
18 ms |
596 KB |
Output is correct |
10 |
Correct |
19 ms |
536 KB |
Output is correct |
11 |
Correct |
19 ms |
484 KB |
Output is correct |
12 |
Correct |
19 ms |
548 KB |
Output is correct |
13 |
Correct |
18 ms |
524 KB |
Output is correct |
14 |
Correct |
19 ms |
596 KB |
Output is correct |
15 |
Correct |
19 ms |
504 KB |
Output is correct |
16 |
Correct |
18 ms |
596 KB |
Output is correct |
17 |
Correct |
19 ms |
564 KB |
Output is correct |
18 |
Correct |
9 ms |
532 KB |
Output is correct |
19 |
Correct |
14 ms |
596 KB |
Output is correct |
20 |
Correct |
52 ms |
588 KB |
Output is correct |
21 |
Correct |
42 ms |
544 KB |
Output is correct |
22 |
Correct |
40 ms |
592 KB |
Output is correct |
23 |
Correct |
11 ms |
596 KB |
Output is correct |
24 |
Correct |
37 ms |
480 KB |
Output is correct |
25 |
Correct |
12 ms |
596 KB |
Output is correct |
26 |
Correct |
19 ms |
580 KB |
Output is correct |
27 |
Correct |
19 ms |
580 KB |
Output is correct |
28 |
Correct |
20 ms |
588 KB |
Output is correct |
29 |
Correct |
20 ms |
476 KB |
Output is correct |
30 |
Correct |
20 ms |
596 KB |
Output is correct |
31 |
Correct |
22 ms |
572 KB |
Output is correct |
32 |
Correct |
20 ms |
596 KB |
Output is correct |
33 |
Correct |
19 ms |
552 KB |
Output is correct |
34 |
Correct |
18 ms |
532 KB |
Output is correct |
35 |
Correct |
22 ms |
3084 KB |
Output is correct |
36 |
Correct |
23 ms |
3028 KB |
Output is correct |
37 |
Execution timed out |
2080 ms |
2932 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
712 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
596 KB |
Output is correct |
4 |
Correct |
8 ms |
596 KB |
Output is correct |
5 |
Correct |
300 ms |
856 KB |
Output is correct |
6 |
Execution timed out |
2081 ms |
20004 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |