Submission #343020

#TimeUsernameProblemLanguageResultExecution timeMemory
343020blueJJOOII 2 (JOI20_ho_t2)C++11
100 / 100
26 ms5356 KiB
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> J(N+1, 0), O(N+1, 0), I(N+1, 0);
    char c;

    for(int i = 1; i <= N; i++)
    {
        cin >> c;
        J[i] = J[i-1];
        O[i] = O[i-1];
        I[i] = I[i-1];

        if(c == 'J') J[i]++;
        else if(c == 'O') O[i]++;
        else if(c == 'I') I[i]++;
    }

    vector<int> dpJ(N+1, 1e9), dpO(N+2, 1e9), dpI(N+1, 1e9);

    int prev = 0;
    for(int i = 1; i <= N; i++)
    {
        if(J[i] < K) continue;

        while(J[i] - J[prev+1] >= K) prev++;
        dpJ[i] = min(dpJ[i-1] + 1, i - prev - K);
    }
    // for(int i = 1; i <= N; i++) cout << dpJ[i] << ' ';
    // cout << '\n';






    prev = N;
    for(int i = N; i >= 1; i--)
    {
        if(I[N] - I[i-1] < K) continue;

        while(I[prev-1] - I[i-1] >= K) prev--;
        dpI[i] = min(dpI[i+1] + 1, prev - (i-1) - K);
    }
    // for(int i = 1; i <= N; i++) cout << dpI[i] << ' ';
    // cout << '\n';

    int res = 1e9;

    int j = 1;
    for(int i = 1; i <= N; i++)
    {
        while(j <= N && O[j] - O[i-1] < K) j++;
        if(j == N+1) break;

        res = min(res, dpJ[i] + j-i-1 - K + dpI[j]);
    }

    if(res == 1e9) cout << "-1\n";
    else cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...