oj.uz

Submission #1114686

# Submission time Handle Problem Language Result Execution time Memory
1114686 2024-11-19T11:28:49 Z AdamGS JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX=2*1e5+7;

int pref[MAX];
int suf[MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    queue<int> indeksy;

    pref[0] = 0;
    for (int i=1; i<=n; i++){
        if (s[i-1]=='J') indeksy.push(i);
        
        if ((int)indeksy.size()<k) pref[i] = -1;
        else if ((int)indeksy.size()==k) pref[i] = i-indeksy.front()-k+1;
        else{
            indeksy.pop();
            pref[i] = i-indeksy.front()-k+1;
        }
    }
    
    indeksy = queue<int>{};
    reverse(s.begin(), s.end());

    suf[n+1] = 0;
    for (int i=0; i<n; i++){
        if (s[i]=='I') indeksy.push(i);
        
        if ((int)indeksy.size()<k) suf[n-i] = -1;
        else if ((int)indeksy.size()==k) suf[n-i] = i-indeksy.front()-k+1;
        else{
            indeksy.pop();
            suf[n-i] = i-indeksy.front()-k+1;
        }
    }

    reverse(s.begin(), s.end());

    //for (int i=0; i<=n; i++) cout << i << " " << pref[i] << " " << suf[i] << endl;

    indeksy = queue<int>{};
    int kon=1, wyn=1e9;

    if (s[0]=='O') indeksy.push(0);

    while (kon<=n){
        kon++;
        if (s[kon-1]=='O') indeksy.push(kon);

        if ((int)indeksy.size() > k) indeksy.pop();

        if ((int)indeksy.size() == k){
            if ((pref[indeksy.front()-1] == -1) or (suf[kon+1] == -1)) continue;
            wyn = min(wyn, pref[indeksy.front()-1]+(kon-indeksy.front()-k+1)+suf[kon+1]);
        }
    }

    if (wyn==1e9) cout << "-1\n";
    else cout << wyn << "\n";

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB Output isn't correct
9 Halted 0 ms 0 KB -