Submission #1310038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310038		syanvu	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	7 ms	5632 KiB

ho_t2

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 1, inf = 1e9, mod = 998244353;

void solve(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = '!' + s;
    vector<int> p[3];
    for(int i = 1; i <= n; i++){
        if(s[i] == 'J') p[0].push_back(i);
        if(s[i] == 'O') p[1].push_back(i);
        if(s[i] == 'I') p[2].push_back(i);
    }
    int dp[n + 2] = {}, dp1[n + 2] = {};
    if(p[0].size() < k || p[1].size() < k || p[2].size() < k){
        cout << -1;
        return;
    }
    for(int i = 0; i <= n + 1; i++) dp[i] = dp1[i] = inf;
    for(int i = 0; i + k - 1 < p[0].size(); i++){
        int l = p[0][i], r = p[0][i + k - 1];
        dp[r] = (r - l + 1) - k;
    }
    for(int i = p[2].size() - 1; i - k + 1 >= 0; i--){
        int r = p[2][i], l = p[2][i - k + 1];
        dp1[l] = (r - l + 1) - k;
    }
    int ans = inf;
    for(int i = 1; i <= n; i++){
        dp[i] = min(dp[i], dp[i - 1] + 1);
    }
    for(int i = n; i >= 1; i--){
        dp1[i] = min(dp1[i], dp1[i + 1] + 1);
    }
    for(int i = 0; i + k - 1 < p[1].size(); i++){
        int l = p[1][i], r = p[1][i + k - 1];
        ans = min(ans, dp[l - 1] + dp1[r + 1] + (r - l + 1) - k);
    }
    if(ans >= inf){
        cout << -1;
        return;
    }
    cout << ans;
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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