Submission #875320

#	Time	Username	Problem	Language	Result	Execution time	Memory
875320		12345678	Boarding Passes (BOI22_passes)	C++17	25 / 100	340 ms	776 KiB

passes

#include <bits/stdc++.h>

using namespace std;

const int nx=1e4+5, kx=10;
int n, cnt, cnt2;
double dp[1<<kx], dpl[nx], dpr[nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    for (int i=1; i<(1<<kx); i++)
    {
        dp[i]=DBL_MAX;
        for (int j=0; j<kx; j++)
        {
            if (i&(1<<j))
            {
                cnt=cnt2=0;
                for (int k=1; k<=n; k++)
                {
                    if (s[k-1]-'A'==j) cnt2++, dpl[k]=dpl[k-1]+cnt+(cnt2-1)/2.0;
                    else if (i&(1<<(s[k-1]-'A'))) cnt++, dpl[k]=dpl[k-1];
                    else dpl[k]=dpl[k-1];
                }
                cnt=cnt2=0;
                for (int k=n; k>=1; k--)
                {
                    if (s[k-1]-'A'==j) cnt2++, dpr[k]=dpr[k+1]+cnt+(cnt2-1)/2.0;
                    else if (i&(1<<(s[k-1]-'A'))) cnt++, dpr[k]=dpr[k+1];
                    else dpr[k]=dpr[k+1];
                }
                //for (int k=1; k<=n; k++) cout<<i<<' '<<dpl[k]<<' '<<dpr[k]<<'\n';
                for (int k=0; k<=n; k++) dp[i]=min(dp[i], dp[i-(1<<j)]+dpl[k]+dpr[k+1]);
            }
        }
        //cout<<"here "<<b<<' '<<dp[i]<<'\n';
    }
    cout<<dp[(1<<kx)-1]<<'\n';
}

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