제출 #1222172

#제출 시각아이디문제언어결과실행 시간메모리
1222172giorgi123glmJJOOII 2 (JOI20_ho_t2)C++20
13 / 100
2095 ms5408 KiB
#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 <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 <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];

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

            for (int _ = 1; _ < K; _++) {
                ans += nJ[ind] - ind - 1;
                ind = nJ[ind];
            }
            for (int _ = 0; _ < K; _++) {
                ans += nO[ind] - ind - 1;
                ind = nO[ind];
            }
            for (int _ = 0; _ < K; _++) {
                ans += nI[ind] - ind - 1;
                ind = nI[ind];
            }

            if (ind <= N)
                actans = min (actans, ans);
        }
    
    if (actans == 2e9)
        cout << -1 << '\n';
    else
        cout << actans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...