Submission #654424

#	Time	Username	Problem	Language	Result	Execution time	Memory
654424		prvocislo	Boarding Passes (BOI22_passes)	C++17	100 / 100	316 ms	17764 KiB

passes

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int g = 15;
vector<int> v[g];
vector<ll> dp((1 << g), 1e18);
vector<ll> pf[g][g]; // pf[i][j][l] = kolko pismen typu j musi prvych l pismen typu i predbehnut
ll c2(ll k)
{
    return k * (k - 1) / 2;
}
void upd(ll& a, ll b)
{
    a = min(a, b);
}
ll eval(int m, int i, int l) // maska, pismeno, kolko ide dolava
{
    ll ans = c2(l) + c2(v[i].size() - l);
    for (int j = 0; j < g; j++) if (m & (1 << j))
    {
        ll fr = pf[i][j][l] * 2ll;
        ll sub = pf[i][j][v[i].size()] - pf[i][j][l];
        ll bk = ((v[i].size() - l) * 1ll * ((ll)v[j].size()) - sub) * 2ll;
        ans += fr + bk;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    for (int a = 0; a < g; a++) for (int b = 0; b < g; b++) pf[a][b].push_back(0ll);
    for (int i = 0; i < s.size(); i++)
    {
        int a = s[i] - 'A'; 
        for (int b = 0; b < g; b++)
        {
            pf[a][b].push_back(pf[a][b].back() + (ll)v[b].size());
        }
        v[a].push_back(i);
    }
    dp[0] = 0;
    for (int m = 0; m < (1 << g); m++)
    {
        for (int i = 0; i < g; i++) if (!(m & (1 << i)))
        {
            int lo = 0, hi = v[i].size();
            while (hi - lo >= 5)
            {
                int m1 = (lo * 2 + hi) / 3, m2 = (lo + hi * 2) / 3;
                if (eval(m, i, m1) < eval(m, i, m2)) hi = m2;
                else lo = m1;
            }
            ll plus = 1e18;
            for (int mi = lo; mi <= hi; mi++) upd(plus, eval(m, i, mi));
            upd(dp[m | (1 << i)], dp[m] + plus);
        }
    }
    cout << dp[(1 << g) - 1] / 2;
    if (dp[(1 << g) - 1] & 1ll) cout << ".5\n";
    else cout << "\n";
    return 0;
}

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

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