oj.uz

답안 #1104284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104284 2024-10-23T11:43:49 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 s;
    cin >> s;

    vector<int> prefix_j(n + 1, 0), prefix_o(n + 1, 0), prefix_i(n + 1, 0);
    vector<int> J, O, I;

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

    int ans = LLONG_MAX;

    for (int i = k - 1; i < O.size(); i++) {
        int o_index = O[i];

        auto it_j = upper_bound(J.begin(), J.end(), o_index) - 1;
        if (it_j < J.begin() + k - 1) continue;

        int last_j = *it_j;
        int j_count = prefix_j[last_j] - prefix_j[last_j - k + 1];

        int i_index = I[i - k + 1];
        auto it_i = upper_bound(I.begin(), I.end(), i_index) - 1;
        if (it_i < I.begin() + k - 1) continue;

        int last_i = *it_i;
        int i_count = prefix_i[last_i] - prefix_i[last_i - k + 1];

        int tmp = (k - j_count) + (k - (prefix_o[O[i]] - prefix_o[O[i - k]])) + (k - i_count);
        ans = min(ans, tmp);
    }

    if (ans == LLONG_MAX) {
        ans = -1;
    }

    cout << ans << endl;
    return 0;
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:26:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = k - 1; i < O.size(); i++) {
      |                         ~~^~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -