Submission #1045387

#TimeUsernameProblemLanguageResultExecution timeMemory
1045387shezittJJOOII 2 (JOI20_ho_t2)C++14
13 / 100
2044 ms5612 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; #define int ll #define fore(a, b, c) for(int a=b; a<c; ++a) #define vi vector<int> #define pb push_back #define ii pair<int,int> #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define endl '\n' #define dbg(x) cerr << #x << ": " << x << endl #define raya cerr << "========================" << endl const int N = 2e5+5; int n, k; string s; int contJ[N], contO[N], contI[N]; int findj(int i){ for(int j=i; j<n; ++j){ int res = contJ[j] - (i == 0 ? 0 : contJ[i-1]); if(res == k) return j; } return -1; } int findl(int j){ for(int l=j+1; l<n; ++l){ int res = contO[l] - contO[j]; if(res == k) return l; } return -1; } int findm(int l){ for(int m=l+1; m<n; ++m){ int res = contI[m] - contI[l]; if(res == k) return m; } return -1; } signed main(){ cin >> n >> k; cin >> s; // contJ for(int i=0; i<n; ++i){ contJ[i] += (s[i] == 'J'); contO[i] += (s[i] == 'O'); contI[i] += (s[i] == 'I'); contJ[i+1] = contJ[i]; contO[i+1] = contO[i]; contI[i+1] = contI[i]; } int ans = n; for(int i=0; i<n; ++i) if(s[i] == 'J'){ // then go to j int j = findj(i); if(j == -1) continue; // then go to l int l = findl(j); if(l == -1) continue; // then go to m int m = findm(l); if(m == -1) continue; int cur = j - i + 1 - k; cur += l - j - k; cur += m - l - k; ans = min(ans, cur); } assert(ans > -1); cout << (ans == n ? -1 : ans) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...