Submission #418037

#	Time	Username	Problem	Language	Result	Execution time	Memory
418037		Chaska	JJOOII 2 (JOI20_ho_t2)	C++11	0 / 100	1 ms	332 KiB

ho_t2

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<long long,long long> ii;
const int N = 6e5+5;
int n,k;
string a;
int J[N],O[N],I[N];
int q;
int howO[N],howI[N],howJ[N];
int main()
{
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    cin >> a;
    q=0;
    for (int i=1;i<=n+n+n;i++) J[i] = O[i] = I[i] = -1;
    
    for (int i=0;i<n;i++) if (a[i]=='J') {
        ++q;
        J[q] = i;
    }
    q=0;
    for (int i=0;i<n;i++) if (a[i]=='O') {
        ++q;
        O[q] = i;
    }
    for (int i=0;i<n;i++) {
        if (a[i]=='O') howO[i]++;
        if (i>0) howO[i] +=howO[i-1];
    }
        q=0;
    for (int i=0;i<n;i++) if (a[i]=='I') {
        ++q;
        I[q] = i;
    }
        for (int i=0;i<n;i++) {
        if (a[i]=='I') howI[i]++;
        if (i>0) howI[i] +=howI[i-1];
    }
            for (int i=0;i<n;i++) {
        if (a[i]=='J') howJ[i]++;
        if (i>0) howJ[i] +=howJ[i-1];
    }
    bool y = false;
    int res = n;
    for (int i=k;i<=n;i++) {
        if (J[i]==-1) i = n+1;
        else {
            int p1 = i-(k-1);
            p1 = J[p1];
            int p2 = J[i];
            int os = howO[J[i]];
            int p3 = p2+1;
            int p4 = O[os+k];
            if (p4 == -1) {
            } else {
                int is = howI[O[os+k]];
                int p5 = p4+1;
                int p6 = I[is+k];
                if (p6 == -1) {
                } else {
                    y = true;
                    int x = howI[p2]-howI[p1] + howO[p2]-howO[p1];
                    int xx = howJ[p4]-howJ[p3] + howI[p4]-howI[p3];
                    int xxx = howJ[p6]-howJ[p5] + howO[p6]-howO[p5];
                    
                    res = min(res,x+xx+xxx);
                }
            }
        }
    }
    if (y) cout << res;
    else cout << -1;
    return 0;
}

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