Submission #815699

#	Time	Username	Problem	Language	Result	Execution time	Memory
815699		anton	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	6964 KiB

ho_t2

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

const int MAX_N = 2*1e5;
const int INF = 1e18;
int n, k;
string s;
int prev2[3][MAX_N];

void find(char c, int j){
    vector<int> oc;
    for(int i = 0; i<n; i++){
        if(s[i] == c){
            oc.push_back(i);
        }
        if(oc.size()>=k){
            prev2[j][i] = oc[oc.size()-k];
        }
        else{
            prev2[j][i] = -INF;
        }
        //cout<<prev2[j][i]<<" ";
    }
    cout<<endl;
}

signed main(){
    cin>>n>>k;
    cin>>s;

    find('J', 0);
    find('O', 1);
    find('I', 2);

    int res= INF;
    for(int i=  0; i<n; i++){
        int cur = i;
        for(int j = 2; j>=0; j--){
            if(cur>=0){
                cur = prev2[j][cur];
            }
        }
        res = min(res, i-cur+1);
    }
    if(res>=INF){
        cout<<-1<<endl;
        return 0;
    }
    cout<<res-3*k<<endl;
}

Compilation message (stderr)

ho_t2.cpp: In function 'void find(char, long long int)':
ho_t2.cpp:19:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   19 |         if(oc.size()>=k){
      |            ~~~~~~~~~^~~

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