Submission #1010369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010369		12345678	Boarding Passes (BOI22_passes)	C++17	100 / 100	308 ms	179640 KiB

passes

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, kx=15;

ll n, p[kx][kx][nx], dp[(1<<kx)+5];
string s;
vector<ll> d[kx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    s=' '+s;
    for (int i=0; i<kx; i++) d[i].push_back(0);
    for (int i=1; i<=n; i++) d[s[i]-'A'].push_back(i);
    for (int i=0; i<kx; i++)
    {
        for (int j=0; j<kx; j++)
        {
            ll v=(i==j)?1:2, tmp=0, cnt=0;
            vector<ll> pref(n+2), suf(n+2);
            for (int k=1; k<=n; k++)
            {
                if (s[k]-'A'==i) cnt+=tmp;
                if (s[k]-'A'==j) tmp+=v;
                pref[k]=cnt;
            }
            tmp=cnt=0;
            for (int k=n; k>=1; k--)
            {
                if (s[k]-'A'==i) cnt+=tmp;
                if (s[k]-'A'==j) tmp+=v;
                suf[k]=cnt;
            }
            for (int k=0; k<=n; k++) p[i][j][k]=pref[k]+suf[k+1];
        }
    }
    for (int i=1; i<(1<<kx); i++)
    {
        dp[i]=LLONG_MAX;
        for (int j=0; j<kx; j++)
        {
            if (i&(1<<j))
            {
                ll l=0, r=d[j].size()-1;
                while (l<r)
                {
                    ll md=(l+r)/2, df=0;
                    for (int k=0; k<kx; k++) if (i&(1<<k)) df+=p[j][k][d[j][md+1]]-p[j][k][d[j][md]];
                    if (df>=0) r=md;
                    else l=md+1;
                }
                //cout<<"here "<<d[j][l]<<'\n';
                ll vl=0;
                for (int k=0; k<kx; k++) if (i&(1<<k)) vl+=p[j][k][d[j][l]];
                dp[i]=min(dp[i], dp[i^(1<<j)]+vl);
            }
        }
        //cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    }
    printf("%.4f\n", dp[((1<<kx)-1)]/2.0);
}

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