Submission #352629

#TimeUsernameProblemLanguageResultExecution timeMemory
352629mariowongJJOOII 2 (JOI20_ho_t2)C++14
0 / 100
1 ms364 KiB
#include <bits/stdc++.h> #define x first #define y second #define pii pair<int,int> #define ll long long #define pll pair<ll,ll> #define pbb pair<bool,bool> #define mp make_pair #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define xmod (ll)(1e9+7) #define hmod 1286031825167LL using namespace std; int n,k,len,pt1,pt2,sum,ans; string s; vector <int> pos[5]; int main(){ ios::sync_with_stdio(false); cin >> n >> k >> s; len=s.length(); for (int i=0;i<len;i++){ if (s[i] == 'J') pos[0].pb(i); if (s[i] == 'O') pos[1].pb(i); if (s[i] == 'I') pos[2].pb(i); } ans=1e9; if (k-1 > (int)pos[1].size()-1 && k-1 > (int)pos[2].size()-1 && k-1 > (int)pos[0].size()-1){ cout << "-1\n"; return 0; } for (int i=1;i<=k-1;i++){ sum+=pos[0][i]-pos[0][i-1]-1; sum+=pos[1][i]-pos[1][i-1]-1; sum+=pos[2][i]-pos[2][i-1]-1; } pt1=k-1; pt2=k-1; for (int i=k-1;i<(int)pos[0].size();i++){ while (pt1 < (int)pos[1].size() && pos[1][pt1-(k-1)] < pos[0][i]){ sum-=(pos[1][pt1-(k-2)]-pos[1][pt1-(k-1)]-1); pt1++; if (pt1 == (int)pos[1].size()) goto out; sum+=(pos[1][pt1]-pos[1][pt1-1]-1); } while (pt2 < (int)pos[2].size() && pos[2][pt2-(k-1)] < pos[1][pt1]){ sum-=(pos[2][pt2-(k-2)]-pos[2][pt2-(k-1)]-1); pt2++; if (pt2 == (int)pos[2].size()) goto out; sum+=(pos[2][pt2]-pos[2][pt2-1]-1); } ans=min(ans,sum+pos[1][pt1-(k-1)]-pos[0][i]-1+pos[2][pt2-(k-1)]-pos[1][pt1]-1); } out:; if (ans == 1e9) cout << "-1\n"; else cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...