Submission #594026

#	Time	Username	Problem	Language	Result	Execution time	Memory
594026		MohammadAghil	Boarding Passes (BOI22_passes)	C++17	100 / 100	187 ms	25256 KiB

passes

#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];
            while(lx + 1 < rx){
                int mid = (lx + rx)>>1;
                ll l = calc(mid), r = calc(mid+1);
                if(l >= r) lx = mid;
                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;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40