Submission #971867

#	Time	Username	Problem	Language	Result	Execution time	Memory
971867		Roumak77	JJOOII 2 (JOI20_ho_t2)	C++17	1 / 100	1 ms	456 KiB

ho_t2

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;

void solve(){
    ll n, k;
    string s;

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

    vector<ll> Os(n + 1, 0);
    vector<ll> Js(n, 1E9);
    vector<ll> Is(n, 1E9);

    // Filling Js and Os

    ll curr = 0;
    ll picked_up = 0;
    vector<ll> temp_list;


    ll req_o = (k + 1)/2;
    ll taken_o = 0;
    ll last = 1E9;

    for(ll i = 0; i < n; i++){
        Os[i + 1] = Os[i];
        last++;
        Js[i] = last;
        if(s[i] == 'O'){
            Os[i + 1]++;
            taken_o++;


        }

        if(s[i] == 'J'){
            temp_list.push_back(i);
            picked_up++;


            if(picked_up > k){
                curr++;
            }
            taken_o = 0;


        }
        if(taken_o >= req_o && picked_up >= k){
            Js[i] = i + 1 - k - req_o - temp_list[curr];
            last =  Js[i];
        }
    }

    curr = 0;
    picked_up = 0;
    temp_list.clear();


    req_o = k/2;
    taken_o = 0;

    last = 1E9;
    ll curr_min = 1E9;


    for(ll i = n - 1; i > 0; i--){
        last++;
        Is[i] = last;
        if(s[i] == 'O'){
            taken_o++;


        }

        if(s[i] == 'I'){
            temp_list.push_back(n - i - 1);
            picked_up++;


            if(picked_up > k){
                curr++;
            }
            taken_o = 0;


        }
        if(taken_o >= req_o && picked_up >= k){
            Is[i] = n - i - k - temp_list[curr] - req_o;
            last = Is[i];
        }
        curr_min = min(Js[i - 1] + Is[i], curr_min);
    }

    if(curr_min >= 1E8){
        cout << - 1;
    }else{
        cout << curr_min;
    }



    //cout << "lol" << endl;



}


int main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;

    while(t--){
        solve();
    }
}

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