Submission #1212428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212428		jerzyk	Chorus (JOI23_chorus)	C++20	100 / 100	5185 ms	43052 KiB

chorus

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<20;
int tab[N];
pair<ll, int> dp[N];

pair<ll, ll> f[N];
vector<int> cur;
int pos = 0; ll dod = 0LL;

pair<ll, int> Get(int a, ll v)
{
    return pair{f[a].st * v + f[a].nd + dod, dp[a].nd};
}

ll It(int a, int b)
{
    ll d = f[a].nd - f[b].nd;
    ll r = f[b].st - f[a].st;
    ll p = (d + r - 1LL) / r;
    if(Get(a, p - 1) <= Get(b, p - 1))
        return p - 1;
    if(Get(a, p) > Get(b, p))
        return p + 1;
    return p; 
}

void Add(int i, int n, ll t)
{
    f[i] = pair{(ll)(n - i), dp[i].st - (ll)(n - i) * t};
    f[i].nd -= dod;
    int m = (int)cur.size() - 1;
    //cout << "\nA: " << i << " : " << f[i].st << " " << f[i].nd << "\n";
    while(m >= pos + 1 && It(i, cur[m]) <= It(cur[m], cur[m - 1]))
    {
        //cout << "D: " << cur.back() << "\n"; 
        --m;
        cur.pop_back();
    }
    //cout << "\n";
    cur.pb(i);
}

void Licz(int n, ll x)
{
    cur.clear();
    multiset<pair<ll, int>> akt;
    akt.insert(dp[0]);
    int il = 0, j = -1; 
    pos = 0; dod = 0LL;
    for(int i = 1; i <= n; ++i)
    {
        dp[i] = pair{I, II};
        il += tab[i] - tab[i - 1] - 1;

        //cerr << "\nL: " << i << " " << il << '\n';

        while(j < min(il, i - 1))
        {
            ++j;
            akt.erase(akt.find(dp[j]));
            Add(j, n, i - 1);
        }
        dod += -(n - il);
        while(pos < (int)cur.size() - 1 && Get(cur[pos], i) >= Get(cur[pos + 1], i))
            ++pos;
        if((int)akt.size() > 0)
            dp[i] = *akt.begin();
        if(pos < (int)cur.size())
            dp[i] = min(dp[i], Get(cur[pos], i));
        --dp[i].nd; dp[i].st += x;
        
        //cout << cur[pos] << "\n";
        //cout << "DP: " << dp[i].st << " " << dp[i].nd << "\n";
        
        akt.insert(dp[i]);
    }
}

ll BS(int n, int x)
{
    ll p = 0, k = 1'000'000'000'000LL, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        //cerr << p << " " << s << " " << k << "\n";
        Licz(n, s);
        if(-dp[n].nd >= x)
            p = s;
        else
            k = s - 1;
    }
    return p;
}

void Solve()
{
    int n, k, cnt = 0;
    string s;
    cin >> n >> k;
    cin >> s;
    for(int i = 1; i <= 2 * n; ++i)
        if(s[i - 1] == 'A')
            tab[++cnt] = i;
    ll x = 4LL, ans = 0LL;
    x = BS(n, k);
    //cout << x << "\n";
    Licz(n, x);
    ans = dp[n].st - (ll)k * x;
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 13 / 13