Submission #654358

#	Time	Username	Problem	Language	Result	Execution time	Memory
654358		AlperenT	Boarding Passes (BOI22_passes)	C++17	60 / 100	2082 ms	3308 KiB

passes

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, G = 15;

int n, g;

double dp[1 << G], pans[N], lft[N], rght[N];

bool vis[N];

string str;

map<char, char> cmprs; 

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 2; i < N; i++) pans[i] = pans[i - 1] + (i - 1) / 2.0;

    for(int i = 0; i < (1 << G); i++) dp[i] = DBL_MAX;
    dp[0] = 0;

    cin >> str;

    n = str.size();

    for(auto c : str) cmprs[c] = '.';

    g = 0;

    for(auto &p : cmprs) p.second = 'A' + (++g - 1);

    for(auto &c : str) c = cmprs[c];

    for(int m = 0; m < (1 << g); m++){
        for(int cur = 0; cur < g; cur++){
            if(m & (1 << cur)) continue;
            else{
                memset(vis, 0, sizeof(vis));

                for(int i = 0; i < n; i++) if(m & (1 << (str[i] - 'A'))) vis[i] = true;

                int totalcnt = count(str.begin(), str.end(), 'A' + cur);

                int curcnt = 0, ptr = 0;

                for(int i = 1; i <= totalcnt; i++){
                    while(str[ptr] != 'A' + cur){
                        if(vis[ptr]) curcnt++;

                        ptr++;
                    }

                    lft[i] = lft[i - 1] + curcnt;

                    ptr++;
                }

                curcnt = 0, ptr = n - 1;

                for(int i = 1; i <= totalcnt; i++){
                    while(str[ptr] != 'A' + cur){
                        if(vis[ptr]) curcnt++;

                        ptr--;
                    }

                    rght[i] = rght[i - 1] + curcnt;

                    ptr--;
                }

                for(int i = 1; i <= totalcnt; i++){
                    lft[i] += pans[i];
                    rght[i] += pans[i];
                }

                for(int i = 0; i <= totalcnt; i++){
                    dp[m | (1 << cur)] = min(dp[m | (1 << cur)], dp[m] + lft[i] + rght[totalcnt - i]);
                }
            }
        }
    }

    cout << fixed << dp[(1 << g) - 1];
}

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