제출 #418037

#제출 시각아이디문제언어결과실행 시간메모리
418037ChaskaJJOOII 2 (JOI20_ho_t2)C++11
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> #define F first #define S second using namespace std; typedef pair<long long,long long> ii; const int N = 6e5+5; int n,k; string a; int J[N],O[N],I[N]; int q; int howO[N],howI[N],howJ[N]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> k; cin >> a; q=0; for (int i=1;i<=n+n+n;i++) J[i] = O[i] = I[i] = -1; for (int i=0;i<n;i++) if (a[i]=='J') { ++q; J[q] = i; } q=0; for (int i=0;i<n;i++) if (a[i]=='O') { ++q; O[q] = i; } for (int i=0;i<n;i++) { if (a[i]=='O') howO[i]++; if (i>0) howO[i] +=howO[i-1]; } q=0; for (int i=0;i<n;i++) if (a[i]=='I') { ++q; I[q] = i; } for (int i=0;i<n;i++) { if (a[i]=='I') howI[i]++; if (i>0) howI[i] +=howI[i-1]; } for (int i=0;i<n;i++) { if (a[i]=='J') howJ[i]++; if (i>0) howJ[i] +=howJ[i-1]; } bool y = false; int res = n; for (int i=k;i<=n;i++) { if (J[i]==-1) i = n+1; else { int p1 = i-(k-1); p1 = J[p1]; int p2 = J[i]; int os = howO[J[i]]; int p3 = p2+1; int p4 = O[os+k]; if (p4 == -1) { } else { int is = howI[O[os+k]]; int p5 = p4+1; int p6 = I[is+k]; if (p6 == -1) { } else { y = true; int x = howI[p2]-howI[p1] + howO[p2]-howO[p1]; int xx = howJ[p4]-howJ[p3] + howI[p4]-howI[p3]; int xxx = howJ[p6]-howJ[p5] + howO[p6]-howO[p5]; res = min(res,x+xx+xxx); } } } } if (y) cout << res; else cout << -1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...