Submission #988217

#	Time	Username	Problem	Language	Result	Execution time	Memory
988217		alexdd	Boarding Passes (BOI22_passes)	C++17	100 / 100	302 ms	14688 KiB

passes

#include<bits/stdc++.h>
using namespace std;
#define int long long
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] = 2*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] = 2*cur;
            }
        }
    }
}
int dp[100005];
void calc_dp()
{
    dp[1]=0;
    for(int i=2;i<=n;i++)
        dp[i] = dp[i-1] + (i-1);
}
int rez[33000];
int calc_sum(int config, int i, int cntle)
{
    int aux=0;
    for(int j=0;j<15;j++)
        if(i!=j && ((1<<j)&config))
            aux += prec[j][i][cntle];
    aux += dp[cntle] + dp[(int)pozs[i].size()-cntle];
    rez[config] = min(rez[config], rez[config-(1<<i)] + aux);
    return aux;
}
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)))
            {
                int st,dr,mij1,mij2;
                st=0;
                dr=pozs[i].size();
                while(dr-st+1>=5)
                {
                    mij1 = st + (dr-st+1)/3;
                    mij2 = mij1 + (dr-st+1)/3;
                    int val1 = calc_sum(config,i,mij1);
                    int val2 = calc_sum(config,i,mij2);
                    if(val1<val2)
                        dr=mij2;
                    else
                        st=mij1;
                }
                for(int j=st;j<=dr;j++)
                    calc_sum(config,i,j);
            }
        }
    }
    if(rez[(1<<15)-1]%2==0) cout<<rez[(1<<15)-1]/2;
    else cout<<rez[(1<<15)-1]/2<<".5";
    return 0;
}

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