Submission #887985

#TimeUsernameProblemLanguageResultExecution timeMemory
887985amirhoseinfar1385JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
7 ms3304 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=200000+10; int n,k; string s; int dpj[maxn],dpo[maxn],dpi[maxn]; int cal(int ind){ if(dpj[ind]==-1||dpo[dpj[ind]]==-1){ return -1; } return dpi[dpo[dpj[ind]]]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; cin>>s; deque<int>v; for(int i=n-1;i>=0;i--){ if(s[i]=='J'){ v.push_front(i); } if((int)v.size()>k){ v.pop_back(); } if((int)v.size()==k){ dpj[i]=v.back(); } else{ dpj[i]=-1; } } v.clear(); for(int i=n-1;i>=0;i--){ if(s[i]=='O'){ v.push_front(i); } if((int)v.size()>k){ v.pop_back(); } if((int)v.size()==k){ dpo[i]=v.back(); } else{ dpo[i]=-1; } } v.clear(); for(int i=n-1;i>=0;i--){ if(s[i]=='I'){ v.push_front(i); } if((int)v.size()>k){ v.pop_back(); } if((int)v.size()==k){ dpi[i]=v.back(); } else{ dpi[i]=-1; } } int f=0,res=n+2; for(int i=0;i<n;i++){ int z=cal(i); if(z!=-1){ // cout<<i<<" "<<z<<"\n"; f=1; res=min(res,z-i+1); } } if(f==0){ cout<<-1<<"\n"; } else{ res-=3*k; cout<<res<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...