Submission #1114688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114688		AdamGS	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	336 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

vector<int> sumki_J(string napis,int k,int n){
    vector<int>wynik(1),sumy(1);
    int suma=0,index=-1;
    bool czybyl=false;
    for(int i=0;i<n;++i){
        if(napis[i]=='J') {
            if(index==-1) index=i;
            suma++;
            
        }
        else{ 
            if(suma>0)
                sumy.push_back(sumy[i]+1);
            else
                sumy.push_back(sumy[i]);
        }
        if(suma==k && napis[i]=='J'){
            czybyl=true;
            sumy.push_back(sumy[i]-sumy[index+1]);
            index=i;
            suma=1;
        }
        else if(napis[i]=='J')
            sumy.push_back(sumy[i]);
        if(czybyl==true)
            wynik.push_back(sumy[i+1]);
        else
            wynik.push_back(-1);
    }
    return wynik;
}
vector<int> sumki_I(string napis,int k,int n){
    vector<int>wynik(1),sumy(1);
    int suma=0,index=-1;
    bool czybyl=false;
    for(int i=n-1;i>=0;--i){
        if(napis[i]=='I') {
            if(index==-1) index=n-i-1;
            suma++;
        }
        else{ 
            if(suma>0)
                sumy.push_back(sumy[n-i-1]+1);
            else
                sumy.push_back(sumy[n-i-1]);
        }
        if(suma==k && napis[i]=='I'){
            czybyl=true;
            sumy.push_back(sumy[n-i-1]-sumy[index+1]);
            index=n-i-1;
            suma=1;
        }
        else if(napis[i]=='I')
            sumy.push_back(sumy[n-i-1]);
        if(czybyl==true)
            wynik.push_back(sumy[n-i]);
        else
            wynik.push_back(-1);
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,k;
    string napis;
    cin >> n >> k;
    cin >> napis;
    vector<int>sum_I=sumki_I(napis,k,n);
    vector<int>sum_J=sumki_J(napis,k,n);
    int suma=0,suma_zjeb=0,wynik=1000000;
    reverse(sum_I.begin(),sum_I.end());
    int i1=-1;
    for(int i=0;i<n;++i){
        if(napis[i]=='O'){
            suma++;
            if(i1==-1)
                i1=i-1;
        } 
        else suma_zjeb++;
        if(suma == k && sum_J[i1+1]!=-1 && sum_I[i+1]!=-1){
            wynik=min(sum_J[i1+1]+sum_I[i+1]+suma_zjeb,wynik);
            //cout << sum_J[i1+1] << ' ' << sum_I[i+1] << endl;
            suma_zjeb=0;
            suma=1;
            i1=i-1;
        }
        else if(suma==k){
            suma_zjeb=0;
            suma=1;
        }
    }
    cout << wynik;
    return 0;
}

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