Submission #977818

#TimeUsernameProblemLanguageResultExecution timeMemory
977818UltraFalconJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
5 ms1172 KiB
#ifndef DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt") #endif #include <bits/stdc++.h> // #define int long long using ll = long long; using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; string s; cin >> s; int lj = 0; while (lj < n && s[lj] != 'J') lj++; int rj = lj; int j_cnt = 1; int cur_cost = 0; while ((rj+1)<n && j_cnt<k) { rj++; j_cnt += s[rj] == 'J'; // cur_cost += s[rj] != 'J'; } int ro = rj; int o_cnt = 0; while ((ro+1)<n && o_cnt < k) { ro++; o_cnt += s[ro] == 'O'; // cur_cost += s[ro] != 'O'; } int ri = ro; int i_cnt = 0; while ((ri+1)<n && i_cnt<k) { ri++; i_cnt += s[ri] == 'I'; } if (j_cnt<k || o_cnt<k || i_cnt<k) { cout << -1 << "\n"; return 0; } cur_cost = (ri-lj+1) - 3*k; int res = cur_cost; while (ri < n) { rj++; while (rj < n && s[rj] != 'J') { // cur_cost += s[rj] != 'J'; o_cnt -= (s[rj]=='O' && rj<=ro); i_cnt -= (s[rj]=='I' && rj > ro && rj<=ri); rj++; } lj++; while (lj<n && s[lj]!='J') { // cur_cost -= s[lj] != 'J'; lj++; } ro = max(ro, rj); while ((ro+1)<n && o_cnt<k) { ro++; o_cnt += s[ro]=='O'; i_cnt -= (s[ro]=='I' && ro<=ri); } ri = max(ri, ro); while ((ri+1)<n && i_cnt<k) { ri++; i_cnt += s[ri]=='I'; } if (rj>=n || ro>=n || ri >= n) break; if (j_cnt<k || o_cnt<k || i_cnt<k) break; cur_cost = (ri-lj+1) - 3*k; res = min(res, cur_cost); } cout << res << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...