Submission #996565

#TimeUsernameProblemLanguageResultExecution timeMemory
996565makravJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
11 ms2660 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define all(a) (a).begin(), (a).end() #define sz(a) (int) a.size() #define pb push_back #define ff first #define sc second #define pii pair<int, int> #define f(i, l, r) for (int i = (l); i < (r); i++) #define double ld signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; string s; cin >> s; vector<int> posj, posi, pref(n + 1); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i]; if (s[i] == 'J') posj.push_back(i); else if (s[i] == 'I') posi.push_back(i); else { pref[i + 1]++; } } int ans = 1e9; int ind = -1; for (int i = 0; i < n; i++) { if (s[i] == 'J' && ind+k<sz(posj)) { ind++; int L = -1, R = sz(posi); while (R - L > 1) { int M = (L + R) / 2; if (M < (k - 1) || posi[M - k + 1] < posj[ind+k-1]) { L = M; continue; } int cntt = pref[posi[M - k + 1]] - pref[posj[ind+k-1]]; if (cntt>=k)R=M; else L=M; } if (R < sz(posi)) ans = min(ans, n - 3 * k - i - (n - posi[R] - 1)); } } cout << (ans == 1e9 ? -1 : ans) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...