Submission #1212462

#TimeUsernameProblemLanguageResultExecution timeMemory
1212462VMaksimoski008JJOOII 2 (JOI20_ho_t2)C++20
100 / 100
20 ms12360 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int get(char ch) { if(ch == 'J') return 0; if(ch == 'O') return 1; return 2; } int vis[N][4], ans=1e9; vector<int> G[N]; void dfs(int u, int t, int l) { if(vis[u][t]) return ; if(t == 3) { ans = min(ans, u-l+1); return ; } for(int v : G[u]) dfs(v, t+1, l); } signed main() { int n, k; cin >> n >> k; string s; cin >> s; s = "." + s; vector<int> pos[3]; for(int i=1; i<=n; i++) pos[get(s[i])].push_back(i); for(int i=0; i<3; i++) { if(pos[i].size() < k) { cout << -1 << '\n'; return 0; } } for(int i=0; i+k-1<pos[2].size(); i++) G[pos[2][i]].push_back(pos[2][i+k-1]); for(int t=0; t<2; t++) { for(int i=0; i+k-1<pos[t].size(); i++) { auto p = lower_bound(pos[t+1].begin(), pos[t+1].end(), pos[t][i+k-1]); if(p != pos[t+1].end()) G[pos[t][i]].push_back(*p); } } for(int i=1; i<=n; i++) if(s[i] == 'J' && !vis[i][0]) dfs(i, 0, i); cout << (ans == 1e9 ? -1 : ans - 3*k) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...