Submission #868615

#	Time	Username	Problem	Language	Result	Execution time	Memory
868615		12345678	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	23 ms	3556 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
int n, k, mp[100], qs[3][nx], res=INT_MAX;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>s;
    mp['J']=0; mp['O']=1; mp['I']=2;
    for (int i=1; i<=n; i++) qs[0][i]=qs[0][i-1], qs[1][i]=qs[1][i-1], qs[2][i]=qs[2][i-1], qs[mp[s[i-1]]][i]++;
    qs[0][n+1]=qs[1][n+1]=qs[2][n+1]=INT_MAX;
    //for (int i=1; i<=n+1; i++) cout<<i<<' '<<qs[0][i]<<' '<<qs[1][i]<<' '<<qs[2][i]<<'\n';
    for (int i=1; i<=n; i++)
    {
        int c=i;
        int v1=lower_bound(qs[0]+1, qs[0]+n+2, qs[0][c-1]+k)-(qs[0])+1;
        int v2=lower_bound(qs[1]+1, qs[1]+n+2, qs[1][v1-1]+k)-(qs[1])+1;
        int v3=lower_bound(qs[2]+1, qs[2]+n+2, qs[2][v2-1]+k)-(qs[2]);
        //cout<<i<<' '<<v1<<' '<<v2<<' '<<v3<<'\n';
        if (v1>=n+1||v2>=n+1||v3>=n+1) continue;
        res=min(res, v3-i+1-3*k);
    } 
    if (res==INT_MAX) cout<<-1;
    else cout<<res;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:14:105: warning: array subscript has type 'char' [-Wchar-subscripts]
   14 |     for (int i=1; i<=n; i++) qs[0][i]=qs[0][i-1], qs[1][i]=qs[1][i-1], qs[2][i]=qs[2][i-1], qs[mp[s[i-1]]][i]++;
      |                                                                                                         ^

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