Submission #996705

#TimeUsernameProblemLanguageResultExecution timeMemory
996705nikaa123JJOOII 2 (JOI20_ho_t2)C++14
100 / 100
13 ms5668 KiB
// #pragma GCC diagnostic warnig "-std=c++11" // #pragma GCC optimize("Ofast") // #pragma GCC optimize ("O3") // #pragma GCC optimization ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define int long long #define eb emplace_back #define mp make_pair #define pb push_back #define pp pop_back #define endl '\n' #define ff first #define ss second #define stop exit(0) #define sz(x) (int)x.size() #define pause system("pause") #define all(x) (x).begin(),(x).end() #define deb(x) cout << #x << "-" << x << endl typedef char chr; typedef string str; // typedef long long ll; typedef vector <int> vii; typedef pair <int,int> pii; const long long INF = LLONG_MAX; const int inf = INT_MAX; const int mod = 998244353; const int MOD = 1e9 + 7; const int dx[] = {0,0,-1,1}; const int dy[] = {-1,1,0,0}; const double PI = 2 * acos(0.0); const int N = 2e5 + 5; int n,k; int ll,rr; string s; int l,r,pos1,pos2,cnt,ans; int pref1[N],pref2[N],pref3[N]; inline void test_case () { cin >> n >> k; cin >> s; s = " " + s; for (int i = 1; i <= n; i++) { pref1[i] = pref1[i-1] + (s[i] == 'J'); pref2[i] = pref2[i-1] + (s[i] == 'O'); pref3[i] = pref3[i-1] + (s[i] == 'I'); } ans = inf; for (int l = 1; l <= n; l++) { if (s[l] != 'J') continue; pos1 = inf; ll = 1; rr = l; while (ll <= rr) { int mid = (ll + rr)/2; if (pref1[l]-pref1[mid-1] >= k) { pos1 = mid; ll = mid + 1; } else { rr = mid - 1; } } if (pos1 == inf) continue; r = inf; ll = l; rr = n; while (ll <= rr) { int mid = (ll + rr)/2; if (pref2[mid]-pref2[l-1] >= k) { r = mid; rr = mid - 1; } else { ll = mid + 1; } } if (r == inf) continue; pos2 = inf; ll = r; rr = n; while (ll <= rr) { int mid = (ll + rr)/2; if (pref3[mid]-pref3[r-1] >= k) { pos2 = mid; rr = mid - 1; } else { ll = mid + 1; } } if (pos2 == inf) continue; // cout << pos1 << " " << l << " " << r << " " << pos2 << " " << pos2 - pos1 + 1 - 3*k << endl; ans = min(ans,pos2-pos1+1-3*k); } if (ans == inf) { cout << -1 << endl; return; } cout << ans << endl; } signed main () { ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int T = 1; // cin >> T; while(T--) { test_case(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...