제출 #734908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734908		adrilen	Boarding Passes (BOI22_passes)	C++17	100 / 100	525 ms	354852 KiB

passes

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<int, int> pii;
constexpr int maxn = 1e5 + 5, maxg = 15;

ll dp[1 << maxg] = { 0 };

ll f[maxn] = { 0 };

ll left_pref[maxn][maxg][maxg] = { 0 }, right_pref[maxn][maxg][maxg] = { 0 };
vector <int> groups[maxg];

int n, g;
// Finding the best way to split the new group given that some groups allready are seated
ll query(int allready, int next_one)
{
    int lower = 0, upper = groups[next_one].size(), mid;
    ll sleft = 0, sright = 0;
    while (lower < upper)
    {
        mid = (lower + upper) >> 1;

        // Testing mid
        sleft = sright = 0;      

        sleft += f[mid] + f[groups[next_one].size() - mid];
        sright += f[mid + 1] + f[groups[next_one].size() - mid - 1];

        for (int y = 0; y < g; y++)
        {
            if ((allready & (1 << y)) == 0) continue;


            if (groups[next_one][mid] != 0) 
                sleft += left_pref[groups[next_one][mid] - 1][next_one][y];
            sleft += right_pref[groups[next_one][mid]][next_one][y];

            if (groups[next_one][mid] + 1 != n) 
                sright += right_pref[groups[next_one][mid] + 1][next_one][y];
            sright += left_pref[groups[next_one][mid]][next_one][y];
        }

        // cout << mid << " " << sleft << " \t" << mid + 1 << " " << sright << "\n";

        if (sleft < sright) upper = mid;
        else lower = mid + 1;
    }
    // cout << allready << " " << next_one << " " << "A" << min(sleft, sright) << "\n";
    return min(sleft, sright);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for (int i = 1; i < maxn - 1; i++) f[i + 1] = f[i] + i; // Double the actual amount


    string s;
    cin >> s;
    n = s.size();
    vector <int> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = s[i] - 'A';
        groups[s[i] - 'A'].emplace_back(i);
        g = max(g, s[i] - 'A' + 1);
    }


    ll sum, seen;
    // Making prefixsum from left
    for (int x = 0; x < g; x++)         // Want to place
    {
        for (int y = 0; y < g; y++)     // Already placed
        {
            if (x == y) continue;
            sum = 0, seen = 0;
            for (int i = 0; i < n; i++)
            {
                if (v[i] == x) sum += seen;
                else if (v[i] == y) seen += 2; // Double the actual amount to keep to integers

                left_pref[i][x][y] = sum; 
                // cout << i << " " << seen << " " << sum << "\n";
            }
        }
    }

    // Making right prefix
    for (int x = 0; x < g; x++)         // Want to place
    {
        for (int y = 0; y < g; y++)     // Already placed
        {
            if (x == y) continue;
            sum = 0, seen = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                if (v[i] == x) sum += seen;
                else if (v[i] == y) seen += 2; // Double the actual amount to keep to integers

                right_pref[i][x][y] = sum;
            }
        }
    }



    // Solving with bitset dp
    ll best;
    for (int i = 0; i < (1 << g); i++)
    {

        best = 2e15;
        for (int y = 0; y < g; y++)
        {
            if (i & (1 << y))
            {
                best = min(best, dp[i - (1 << y)] + query(i - (1 << y), y));
                // Update best
            }
        }
        if (best == 2e15) best = 0;
        dp[i] = best;
    }
    cout << dp[(1 << g) - 1] / 2;
    if (dp[(1 << g) - 1] & 1) cout << ".5";
    cout << "\n";

}

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