제출 #875322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875322		12345678	Boarding Passes (BOI22_passes)	C++17	55 / 100	1174 ms	1140 KiB

passes

#include <bits/stdc++.h>

using namespace std;

const int nx=1e4+5, kx=11;
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=0; k<=n; k++) dp[i]=min(dp[i], dp[i-(1<<j)]+dpl[k]+dpr[k+1]);
            }
        }
    }
    printf("%.4f", dp[(1<<kx)-1]);
}

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