Submission #202452

#	Time	Username	Problem	Language	Result	Execution time	Memory
202452		Kastanda	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	43 ms	5368 KiB

ho_t2

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, k, P[3][N], Nxt[3][N];
char S[N];
int main()
{
    scanf("%d%d%s", &n, &k, S + 1);
    S[++ n] = 'J';
    for (int i = 1; i <= n; i ++)
    {
        if (S[i] == 'J') S[i] = 0;
        if (S[i] == 'O') S[i] = 1;
        if (S[i] == 'I') S[i] = 2;
    }
    for (int w = 0; w <= 2; w ++)
        for (int i = 1; i <= n; i ++)
            P[w][i] = P[w][i - 1] + (S[i] == w);
    for (int w = 0; w <= 2; w ++)
        for (int i = 1; i <= n; i ++)
            Nxt[w][i] = lower_bound(P[w], P[w] + n + 1, P[w][i - 1] + k) - P[w];
    int Mn = n + 1;
    for (int l = 1; l <= n; l ++)
    {
        int nw = l;
        for (int w = 0; w <= 2; w ++)
            if (nw <= n)
                nw = Nxt[w][nw] + 1;
        if (nw <= n)
            Mn = min(Mn, nw - l - k * 3);
    }
    if (Mn > n)
        Mn = -1;
    return !printf("%d\n", Mn);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%s", &n, &k, S + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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