Submission #1045388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045388		shezitt	JJOOII 2 (JOI20_ho_t2)	C++14	13 / 100	2017 ms	5604 KiB

ho_t2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

#define int ll 
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define ii pair<int,int>
#define F first 
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "========================" << endl

const int N = 2e5+5;

int n, k;
string s;

int contJ[N], contO[N], contI[N];

int findj(int i){
    for(int j=i; j<n; ++j){
        int res = contJ[j] - (i == 0 ? 0 : contJ[i-1]);
        if(res == k) return j;
    }
    return -1;
}

int findl(int j){
    for(int l=j+1; l<n; ++l){
        int res = contO[l] - contO[j];
        if(res == k) return l;
    }
    return -1;
}

int findm(int l){
    for(int m=l+1; m<n; ++m){
        int res = contI[m] - contI[l];
        if(res == k) return m;
    }
    return -1;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    cin >> s;

    // contJ
    for(int i=0; i<n; ++i){

        contJ[i] += (s[i] == 'J');
        contO[i] += (s[i] == 'O');
        contI[i] += (s[i] == 'I');

        contJ[i+1] = contJ[i];
        contO[i+1] = contO[i];
        contI[i+1] = contI[i];
    }

    int ans = n;

    for(int i=0; i<n; ++i) if(s[i] == 'J'){

        // then go to j
        int j = findj(i);
        if(j == -1) continue;
        // then go to l
        int l = findl(j);
        if(l == -1) continue;
        // then go to m
        int m = findm(l);
        if(m == -1) continue;

        int cur = j - i + 1 - k;
        cur += l - j - k;
        cur += m - l - k;
        ans = min(ans, cur);

    }

    // assert(ans > -1);
    cout << (ans == n ? -1 : ans) << endl;

}

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