Submission #1104270

#TimeUsernameProblemLanguageResultExecution timeMemory
1104270zephyrionJJOOII 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 s1; cin >> s1; string s2 = ""; for (int i = 0; i < k; i++){ s2 += 'J'; } for (int i = 0; i < k; i++){ s2 += 'O'; } for (int i = 0; i < k; i++){ s2 += 'I'; } 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; } else{ bool valid = true; for (int j = 0; j < k; j++) { if (s1[i + k + j] != 'O' || s1[i + 2 * k + j] != 'I') { valid = false; break; } } if (!valid){ continue; } else{ int tmp = 0; int j_start = i; int j_end = i + k; int j_count = prefix_j[j_end] - prefix_j[j_start]; tmp += k - j_count; int o_start = i + k; int o_end = i + 2 * k; int o_count = prefix_o[o_end] - prefix_o[o_start]; tmp += k - o_count; int i_start = i + 2 * k; int i_end = i + 3 * k; int i_count = prefix_i[i_end] - prefix_i[i_start]; tmp += k - i_count; ans = min(ans, tmp); } } } if (ans == INT_MAX) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...