Submission #1104284

#TimeUsernameProblemLanguageResultExecution timeMemory
1104284zephyrionJJOOII 2 (JOI20_ho_t2)C++17
0 / 100
1 ms336 KiB
#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 (stderr)

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++) {
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...