Submission #737703

#	Time	Username	Problem	Language	Result	Execution time	Memory
737703		snowman	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	2012 KiB

ho_t2

#include <bits/stdc++.h>
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}



const int mxa = 1e9 + 1;
// string __fname = "exclusiv";  
// ifstream in(__fname + ".in"); 
// ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out


void solve(){
	int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vii a(3);
    fri(0, n){
        if(s[i] == 'J'){
            a[0].pb(i);
        }
        else if(s[i] == 'O'){
            a[1].pb(i);
        }
        else a[2].pb(i);
    }
    int rs = INT_MAX;
    for(int i = 0; i <= sz(a[0]) - k; i++){
        int o = a[0][i + k - 1] + 1;
        auto it = lower_bound(all(a[1]), o);
        int idx = it - a[1].begin();
        if(idx + k - 1 >= sz(a[1])){
            break;
        }
        int I = a[1][idx + k - 1] + 1;
        auto it2 = lower_bound(all(a[2]), I);
        int id = it2 - a[2].begin();
        if(id + k - 1 >= sz(a[2])){
            break;
        }
        else{
            rs = min(rs, a[2][id + k - 1] - a[0][i] - k * 3 + 1);
        }
    }
    if(rs == INT_MAX){
        cout << -1 << '\n';
    }
    else cout << rs << '\n';
}


int main()
{   
    ios_base::sync_with_stdio(0); cin.tie(0); ct(fixed); ct(setprecision(10)); 
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    return 0;
}

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