제출 #598647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598647		someone	Boarding Passes (BOI22_passes)	C++14	60 / 100	2066 ms	2504 KiB

passes

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 42, G = 15, INF = 1e18 + 42;

string str;
vector<int> pos[G];
int n, g = 0, sum[N], val[N], dp[1 << G];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> str;
    n = str.size();
    for(int i = 0; i < n; i++)
        g = max(g, (int)(str[i] - 'A' + 1));
    for(int i = 0; i < n; i++)
        pos[str[i] - 'A'].push_back(i);
    for(int i = 1; i < (1 << g); i++) {
        dp[i] = INF;
        for(int j = 0; j < n; j++)
            sum[j] = 0;
        for(int j = 0; j < g; j++)
            if(i & (1 << j))
                for(int p : pos[j])
                    sum[p]++;
        for(int j = 1; j < n; j++)
            sum[j] += sum[j-1];
            
        for(int j = 0; j < g; j++)
            if(i & (1 << j)) {
                int sz = pos[j].size(), tot = 0, mini = INF;
                for(int k = 0; k < sz; k++)
                    tot += sum[pos[j][k]] - (k+1);
                mini = tot*4 + (sz*(sz-1));
                for(int k = sz-1; k > -1; k--) {
                    tot += sum[n-1] - sum[pos[j][k]] * 2 - sz + 2 * (k+1);
                    mini = min(mini, tot*4 + (k*(k-1)+(sz-k)*(sz-k-1)));
                }
                dp[i] = min(dp[i], dp[i ^ (1 << j)] + mini);
            }
    }
    cout << setprecision(30) << dp[(1 << g) - 1]/4.0;
}

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