Submission #343020

#	Time	Username	Problem	Language	Result	Execution time	Memory
343020		blue	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	26 ms	5356 KiB

ho_t2

#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';
}

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