Submission #1222181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222181		giorgi123glm	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	318 ms	216696 KiB

ho_t2

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
using namespace std;

#define int long long

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0, K = 0;
    cin >> N >> K;

    string str = "";
    cin >> str;

    str = " " + str;

    vector <int> nJ (N + 2);
    nJ[N] = nJ[N + 1] = N + 1;
    for (int i = N - 1; i >= 1; i--)
        if (str[i + 1] == 'J')
            nJ[i] = i + 1;
        else
            nJ[i] = nJ[i + 1];

    vector <vector <pair <int, int> > > binJ (
        N + 2,
        vector <pair <int, int> > (20)
    );
    for (int p = 0; p <= 19; p++)
        if (p == 0)
            for (int i = N + 1; i >= 1; i--)
                binJ[i][0] = {nJ[i], nJ[i] - i - 1};
        else
            for (int i = N + 1; i >= 1; i--)
                binJ[i][p] = {
                    binJ[
                        binJ[i][p - 1].first
                    ][p - 1].first,
                    binJ[i][p - 1].second +
                    binJ[
                        binJ[i][p - 1].first
                    ][p - 1].second
                };

    vector <int> nO (N + 2);
    nO[N] = nO[N + 1] = N + 1;
    for (int i = N - 1; i >= 1; i--)
        if (str[i + 1] == 'O')
            nO[i] = i + 1;
        else
            nO[i] = nO[i + 1];

    vector <vector <pair <int, int> > > binO (
        N + 2,
        vector <pair <int, int> > (20)
    );
    for (int p = 0; p <= 19; p++)
        if (p == 0)
            for (int i = N + 1; i >= 1; i--)
                binO[i][0] = {nO[i], nO[i] - i - 1};
        else
            for (int i = N + 1; i >= 1; i--)
                binO[i][p] = {
                    binO[
                        binO[i][p - 1].first
                    ][p - 1].first,
                    binO[i][p - 1].second +
                    binO[
                        binO[i][p - 1].first
                    ][p - 1].second
                };

    vector <int> nI (N + 2);
    nI[N] = nI[N + 1] = N + 1;
    for (int i = N - 1; i >= 1; i--)
        if (str[i + 1] == 'I')
            nI[i] = i + 1;
        else
            nI[i] = nI[i + 1];

    vector <vector <pair <int, int> > > binI (
        N + 2,
        vector <pair <int, int> > (20)
    );
    for (int p = 0; p <= 19; p++)
        if (p == 0)
            for (int i = N + 1; i >= 1; i--)
                binI[i][0] = {nI[i], nI[i] - i - 1};
        else
            for (int i = N + 1; i >= 1; i--)
                binI[i][p] = {
                    binI[
                    binI[i][p - 1].first
                    ][p - 1].first,
                    binI[i][p - 1].second +
                    binI[
                        binI[i][p - 1].first
                    ][p - 1].second
                };

    int actans = 2e9;
    for (int i = N - 2; i >= 1; i--)
        if (str[i] == 'J') {
            int ind = i;
            int ans = 0;

            for (int p = 19; p >= 0; p--)
                if ((K - 1) & (1 << p)) {
                    ans += binJ[ind][p].second;
                    ind = binJ[ind][p].first;
                }
            for (int p = 19; p >= 0; p--)
                if (K & (1 << p)) {
                    ans += binO[ind][p].second;
                    ind = binO[ind][p].first;
                }
            for (int p = 19; p >= 0; p--)
                if (K & (1 << p)) {
                    ans += binI[ind][p].second;
                    ind = binI[ind][p].first;
                }

            if (ind <= N)
                actans = min (actans, ans);
        }
    
    if (actans == 2e9)
        cout << -1 << '\n';
    else
        cout << actans << '\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87