Submission #1164010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164010		cow123	Boarding Passes (BOI22_passes)	C++20	100 / 100	519 ms	381040 KiB

passes

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb push_back
#define d long double
#define int long long
using namespace std;
vector<int> wart,odwart;
const int maxn = 100 * 1000 + 5;
const int stala = 15;
vector<int> zlicz[maxn];
int pref[maxn][stala],prefp[maxn][stala][stala],suf[maxn][stala],sufp[maxn][stala][stala];
const int maxg = (1 << stala);
d dp[maxg];
bool check(int poz,int typ,int maska){
    int poz1 = zlicz[typ][poz];
    int k1 = 0,k2 = 0;
    FOR(j,0,stala){
        if(((1 << j) & maska)){
            k1+=pref[poz1][j];
            k2+=suf[poz1][j];
        }
    }
    k1*=2;
    k2*=2;
    k1+=pref[poz1][typ];
    k2+=suf[poz1][typ];
    if(k1 < k2){
        return true;
    }
    return false;
}
int32_t main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    string W;
    cin>>W;
    for(auto y : W){
        wart.pb(y - 'A');
    }
    FOR(i,0,W.size()){
        zlicz[W[i] - 'A'].pb(i);
    }
    int n = W.size();
    FOR(i,0,wart.size()){
        pref[i][wart[i]]++;
        FOR(j,0,stala){
            pref[i + 1][j] = pref[i][j];
        }
    }
    for(int i = n - 1; i >= 0;--i){
        suf[i][wart[i]]++;
        if(i == 0){continue;}
        FOR(j,0,stala){
            suf[i - 1][j] = suf[i][j];
        }
    }
    FOR(i,0,stala){
        FOR(j,0,stala){
            FOR(k,0,n){
                if(wart[k] == i){
                    prefp[k][i][j]+=pref[k][j];
                }
                prefp[k + 1][i][j]+=prefp[k][i][j];
            }
        }
    }
    FOR(i,0,stala){
        FOR(j,0,stala){
            for(int k = n - 1; k >= 0;--k){
                if(wart[k] == i){
                    sufp[k][i][j]+=suf[k][j];
                }
                if(k == 0){continue;}
                sufp[k - 1][i][j]+=sufp[k][i][j];
            }
        }
    }
    FOR(i,0,maxg){
        dp[i] = 3e9;
    }
    dp[0] = 0;
    FOR(i,0,maxg){
        FOR(j,0,stala){
            if(((1 << j) & (i)) == 0){
                if(zlicz[j].size() == 0){
                    dp[i + (1 << j)] = min(dp[i + (1 << j)],dp[i]);
                }else{
                    int kon = zlicz[j].size(),poc = 0;
                    for(int sro = (poc + kon) / 2; sro > 0;sro/=2){
                        while(poc + sro < kon && check(poc + sro,j,i)){
                            poc+=sro;
                        }
                    }
                    d prawo = 0;
                    d odp = (poc) * (poc + 1);
                    bool b = false;
                    if(poc + 1 < zlicz[j].size()){
                        odp+=(zlicz[j].size() - poc - 1) * (zlicz[j].size() - poc - 2);
                        b = true;
                    }    
                    int srodek = zlicz[j][poc];
                    prawo+=(zlicz[j].size()) * (zlicz[j].size() - 1);
                    odp/=4;
                    prawo/=4;
                    FOR(k,0,stala){
                        if(((1 << k) & i)){
                            prawo+=sufp[0][j][k];
                            if(!b){
                                odp+=prefp[srodek][j][k];             
                            }else{
                                odp+=prefp[srodek][j][k];
                                odp+=sufp[srodek + 1][j][k];    
                            }
                        }
                    }
                   // cout<<prawo <<" " <<odp <<"\n";
                    // if(i == 2 && j == 2){
                    //     cout<<prawo <<" " <<odp <<" " <<srodek <<" " <<zlicz[j].size()  <<"\n";
                    // }
                    dp[i + (1 << j)] = min(dp[i + (1 << j)],dp[i] + min(odp,prawo));
                }
            }
        }
    }
    cout<<fixed <<setprecision(3) <<dp[maxg - 1];
}

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