Submission #977281

#TimeUsernameProblemLanguageResultExecution timeMemory
977281LOLOLOJJOOII 2 (JOI20_ho_t2)C++17
1 / 100
1 ms604 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e3 + 100; int pr[N], suff[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector <int> pos; deque <int> dq; int n, k; cin >> n >> k; string s; cin >> s; s = 'a' + s; for (int i = 1; i <= n; i++) { if (s[i] == 'O') pos.pb(i); pr[i] = -1; if (s[i] == 'J') { dq.push_back(i); } if (sz(dq) > k) { dq.pop_front(); } if (sz(dq) == k) { pr[i] = dq.front(); } } while (sz(dq)) dq.pop_back(); for (int i = n; i >= 1; i--) { suff[i] = -1; if (s[i] == 'I') { dq.push_back(i); } if (sz(dq) > k) dq.pop_front(); if (sz(dq) == k) { suff[i] = dq.front(); } } int ans = n + 1; for (int i = k - 1; i < sz(pos); i++) { int r = suff[pos[i]], l = pr[pos[i - k + 1]]; if (r != -1 && l != -1) { ans = min(ans, r - l + 1 - k * 3); } } if (ans == n + 1) ans = -1; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...