oj.uz

Submission #1104275

# Submission time Handle Problem Language Result Execution time Memory
1104275 2024-10-23T11:28:14 Z zephyrion JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n, k;
    cin >> n >> k;
    string s1;
    cin >> s1;
    vector<int> prefix_j(n + 1, 0), prefix_o(n + 1, 0), prefix_i(n + 1, 0);

    for (int i = 0; i < n; i++) {
        prefix_j[i + 1] = prefix_j[i] + (s1[i] == 'J');
        prefix_o[i + 1] = prefix_o[i] + (s1[i] == 'O');
        prefix_i[i + 1] = prefix_i[i] + (s1[i] == 'I');
    }

    int ans = INT_MAX;

    for (int i = 0; i <= n - 3 * k; i++) {
        if (s1[i] != 'J') continue;

        bool valid = true;

        if ((prefix_o[i + k] - prefix_o[i]) < k || (prefix_i[i + 2 * k] - prefix_i[i + k]) < k) {
            valid = false;
        }

        if (!valid) continue;

        int tmp = 0;

        tmp += k - (prefix_j[i + k] - prefix_j[i]);
        
        int o_start = i + k;
        int o_end = o_start + k - 1;
        tmp += k - (prefix_o[o_end + 1] - prefix_o[o_start]);

        int i_start = o_end + 1;
        int i_end = i_start + k - 1;
        tmp += k - (prefix_i[i_end + 1] - prefix_i[i_start]);

        ans = min(ans, tmp);
    }

    if (ans == INT_MAX){
        cout << -1;
    }
    else{
        cout << ans;
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -