oj.uz

Submission #971867

# Submission time Handle Problem Language Result Execution time Memory
971867 2024-04-29T12:13:40 Z Roumak77 JJOOII 2 (JOI20_ho_t2) C++17
1 / 100
 1 ms 456 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -