Submission #988214

#	Time	Username	Problem	Language	Result	Execution time	Memory
988214		alexdd	Boarding Passes (BOI22_passes)	C++17	25 / 100	2062 ms	12744 KiB

passes

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
const int INF = 1e18;

int n;
string s;
vector<int> pozs[20];

vector<int> prec[15][15];
int pref[100005];
void calc_prec()
{
    for(int p=0;p<15;p++)
    {
        pref[0]=0;
        for(int i=1;i<=n;i++)
        {
            pref[i]=pref[i-1];
            if(s[i-1]-'A'==p)
                pref[i]++;
        }
        for(int u=0;u<15;u++)
        {
            if(u==p)
                continue;
            prec[p][u].resize((int)pozs[u].size()+2);
            int cur=0;
            for(auto x:pozs[u])
                cur += pref[n]-pref[x];
            prec[p][u][0] = cur;
            for(int i=1;i<=(int)pozs[u].size();i++)
            {
                cur -= pref[n]-pref[pozs[u][i-1]];
                cur += pref[pozs[u][i-1]];
                prec[p][u][i] = cur;
            }
        }
    }
}
ld dp[100005];
void calc_dp()
{
    dp[1]=0;
    for(int i=2;i<=n;i++)
    {
        dp[i] = dp[i-1] + (ld)(i-1)/2;
        //cout<<i<<" "<<dp[i]<<"\n";
    }
}
ld rez[33000];
signed main()
{
    cin>>s;
    n=s.size();
    for(int i=1;i<=n;i++)
        pozs[s[i-1]-'A'].push_back(i);
    calc_prec();
    calc_dp();
    for(int config=1;config<(1<<15);config++)
    {
        rez[config]=INF;
        for(int i=0;i<15;i++)
        {
            if((((1<<i)&config)))
            {
                for(int cntle=0;cntle<=(int)pozs[i].size();cntle++)
                {
                    int aux=0;
                    for(int j=0;j<15;j++)
                        if(i!=j && ((1<<j)&config))
                            aux += prec[j][i][cntle];
                    rez[config] = min(rez[config], (ld)rez[config-(1<<i)] + (ld)aux + dp[cntle] + dp[(int)pozs[i].size()-cntle]);
                }
            }
        }
    }
    cout<<fixed<<setprecision(6)<<rez[(1<<15)-1];
    return 0;
}

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