Submission #573466

#TimeUsernameProblemLanguageResultExecution timeMemory
573466tekiJJOOII 2 (JOI20_ho_t2)C++11
100 / 100
28 ms3288 KiB
#include <bits/stdc++.h> typedef long long ll; #define pb push_back #define MS(x,y) memset((x),(y),sizeof((x))) #define MN 1000000007 using namespace std; int main() { #if LOCAL_DEBUG fstream cin("in.txt"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; int pref[3][n+5]; MS(pref,0); /// J pa O pa I string s; cin>>s; for (int i = 0; i<n; i++) { pref[0][i+1] = pref[0][i] + (s[i] == 'J'); pref[1][i+1] = pref[1][i] + (s[i] == 'O'); pref[2][i+1] = pref[2][i] + (s[i] == 'I'); } int curr[3]; int res = INT_MAX/2; for (int i = 0; i<=n; i++) { for (int j = 0; j<3; j++) curr[j] = pref[j][i]; int newPos = i; int resC = 0; for (int j = 0; j<3; j++) { auto itJ = lower_bound(pref[j]+newPos,pref[j]+(n+1),curr[j]+k); if (itJ == pref[j]+(n+1)) {resC = INT_MAX/2; break; } newPos = itJ-pref[j]; for (int k = 0; k<3; k++) if (k != j) resC += pref[k][newPos]-curr[k]; for (int k = 0; k<3; k++) curr[k] = pref[k][newPos]; } res = min(res,resC); } if (res != INT_MAX/2) cout<<res<<endl; else cout<<-1<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...