Submission #1191800

#TimeUsernameProblemLanguageResultExecution timeMemory
1191800bestbestJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
19 ms3088 KiB
#include <bits/stdc++.h> using namespace std; #define en '\n' #define sp ' ' typedef long long ll; #define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pii pair<int,int> const int N=2e5+10; const ll M=1e9+7; int n,k; string s; int sj[N],so[N],si[N]; int mi=M; int sum; int main(){Linux cin >> n >> k; cin >> s; s='0'+s; for(int i=1;i<=n;i++){ if(s[i]=='J')sj[i]++; else if(s[i]=='O')so[i]++; else si[i]++; sj[i]+=sj[i-1]; so[i]+=so[i-1]; si[i]+=si[i-1]; // cout << sj[i] << ',' << so[i] << ',' << si[i] << sp; } sj[n+1]=sj[n]; so[n+1]=so[n]; si[n+1]=si[n]; // cout << (lower_bound(sj,sj+n+1,3)-sj) << en; for(int i=1;i<=n;i++){ // cout << i << sp; sum=0; int it1=lower_bound(sj,sj+n+1,sj[i-1]+k)-sj; if(it1<=n){ sum+=it1-i+1-sj[it1]+sj[i-1]; // cout << it1 << sp; int it2=lower_bound(so,so+n+1,so[it1]+k)-so; if(it2<=n){ sum+=it2-it1-so[it2]+so[it1]; // cout << it2 << sp; int it3=lower_bound(si,si+n+1,si[it2]+k)-si; if(it3<=n){ sum+=it3-it2-si[it3]+si[it2]; // cout << it3 << sp; } else continue; } else continue; } else continue; // cout << sum << en; mi=min(mi,sum); } if(mi==M)cout << -1 << en; else cout << mi << en; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...