Submission #997153

#TimeUsernameProblemLanguageResultExecution timeMemory
997153giorgi_pkhaladzeJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
10 ms3612 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define ff first #define ss second using namespace std; vector <int> j,o,i; int n,m,k,ans,a[200001],ph[200001],sh[200001]; string s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; cin>>s; s=' '+s; /*if(m*3>n){ cout<<-1; return 0; } */ for(k=1; k<=n; k++){ ph[k]=ph[k-1]; if(s[k]=='J')ph[k]++,j.pb(k); if(s[k]=='I')i.pb(k); if(s[k]=='O')o.pb(k); } for(k=n; k>0; k--){ sh[k]=sh[k+1]; if(s[k]=='I')sh[k]++; } if((int)j.size()<m || (int)o.size()<m || (int)i.size()<m) { cout<<-1; return 0; } //cout<<"GIO"; return 0; int ans=10000000; for(k=0; k<=(int)o.size()-m; k++){ //cout<<sh[o[k]]<<" "<<ph[o[k]]<<'\n'; //if(sh[o[k]]<m)break; //if(ph[o[k]]>m)break; int pos1=lower_bound(j.begin(),j.end(),o[k])-1-j.begin(); int pos2=lower_bound(i.begin(),i.end(),o[k+m-1])-i.begin(); int sz=j[pos1]-j[pos1-m+1]-m; if(pos1<m-1 || pos2>(int)i.size()-m)continue; //cout<<pos1+1<<" "<<pos2+1<<'\n'; sz++; //cout<<sz<<'\n'; sz+=i[pos2+m-1]-i[pos2]-m+1; //cout<<sz<<'\n'; sz+=o[k+m-1]-o[k]-m+1; //ans=min(ans,sz); //cout<<ans<<'\n'; ans=min(ans,i[pos2+m-1]-j[1+pos1-m]+1-3*m); } if(ans==10000000)cout<<-1; else cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...