제출 #1355719

#제출 시각아이디문제언어결과실행 시간메모리
1355719AliyyiakbarJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
8 ms3016 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, k;
    string s;
    cin >> n >> k >> s;
    map<char, vector<int>> pos;
    for (int i = 0; i < n; ++i)
    {
        pos[s[i]].push_back(i);
    }
    int res = INF;
    for (int i = 0; i + k - 1 < (int)pos['J'].size(); ++i)
    {
        // pos['J'][i] --> first J
        // pos['J'][i + k - 1] --> last J
        int first_o = lower_bound(pos['O'].begin(), pos['O'].end(), pos['J'][i + k - 1]) - pos['O'].begin();
        if (first_o + k - 1 >= (int)pos['O'].size())
        {
            continue;
        }
        // pos['O'][o + k - 1] --> last o
        int first_i = lower_bound(pos['I'].begin(), pos['I'].end(), pos['O'][first_o + k - 1]) - pos['I'].begin();
        // pos['I'][first_i + k - 1] --> last I
        if (first_i + k - 1 >= (int)pos['I'].size())
        {
            continue;
        }
        res = min(res, pos['I'][first_i + k - 1] - pos['J'][i] + 1 - 3 * k);
    }
    cout << (res == INF ? -1 : res) << '\n';
}
//
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...