oj.uz

Submission #1114688

# Submission time Handle Problem Language Result Execution time Memory
1114688 2024-11-19T11:47:09 Z AdamGS JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 336 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -