| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 206967 |
2020-03-06T02:11:46 Z |
wiwiho |
JJOOII 2 (JOI20_ho_t2) |
C++14 |
|
38 ms |
3136 KB |
//#define NDEBUG
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a) / (b) + !!((a) % (b)))
//#define TEST
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
int main(){
StarBurstStream
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = ' ' + s;
vector<int> J(n + 1), O(n + 1), I(n + 1);
for(int i = 1; i <= n; i++){
if(s[i] == 'J') J[i]++;
else if(s[i] == 'O') O[i]++;
else I[i]++;
J[i] += J[i - 1];
O[i] += O[i - 1];
I[i] += I[i - 1];
}
int ans = MAX;
for(int i = 1; i <= n && J[n] - J[i - 1] >= k && O[n] - O[i - 1] >= k && I[n] - I[i - 1] >= k; i++){
int l = lower_bound(iter(J), J[i - 1] + k) - J.begin();
if(O[n] - O[l] < k || I[n] - I[l] < k) continue;
int m = lower_bound(iter(O), O[l] + k) - O.begin();
if(I[n] - I[m] < k) continue;
int r = lower_bound(iter(I), I[m] + k) - I.begin();
int now = 0;
now += J[l] - J[i - 1] - k + O[l] - O[i - 1] + I[l] - I[i - 1];
now += J[m] - J[l] + O[m] - O[l] - k + I[m] - I[l];
now += J[r] - J[m] + O[r] - O[m] + I[r] - I[m] - k;
ans = min(ans, now);
}
if(ans == MAX) ans = -1;
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
4 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
4 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
376 KB |
Output is correct |
| 17 |
Correct |
5 ms |
376 KB |
Output is correct |
| 18 |
Correct |
5 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
5 ms |
376 KB |
Output is correct |
| 21 |
Correct |
5 ms |
376 KB |
Output is correct |
| 22 |
Correct |
5 ms |
376 KB |
Output is correct |
| 23 |
Correct |
5 ms |
508 KB |
Output is correct |
| 24 |
Correct |
5 ms |
376 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
5 ms |
376 KB |
Output is correct |
| 27 |
Correct |
5 ms |
376 KB |
Output is correct |
| 28 |
Correct |
5 ms |
376 KB |
Output is correct |
| 29 |
Correct |
5 ms |
376 KB |
Output is correct |
| 30 |
Correct |
5 ms |
376 KB |
Output is correct |
| 31 |
Correct |
5 ms |
376 KB |
Output is correct |
| 32 |
Correct |
5 ms |
376 KB |
Output is correct |
| 33 |
Correct |
5 ms |
376 KB |
Output is correct |
| 34 |
Correct |
5 ms |
376 KB |
Output is correct |
| 35 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
4 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
248 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
4 ms |
376 KB |
Output is correct |
| 14 |
Correct |
5 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
376 KB |
Output is correct |
| 17 |
Correct |
5 ms |
376 KB |
Output is correct |
| 18 |
Correct |
5 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
5 ms |
376 KB |
Output is correct |
| 21 |
Correct |
5 ms |
376 KB |
Output is correct |
| 22 |
Correct |
5 ms |
376 KB |
Output is correct |
| 23 |
Correct |
5 ms |
508 KB |
Output is correct |
| 24 |
Correct |
5 ms |
376 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
5 ms |
376 KB |
Output is correct |
| 27 |
Correct |
5 ms |
376 KB |
Output is correct |
| 28 |
Correct |
5 ms |
376 KB |
Output is correct |
| 29 |
Correct |
5 ms |
376 KB |
Output is correct |
| 30 |
Correct |
5 ms |
376 KB |
Output is correct |
| 31 |
Correct |
5 ms |
376 KB |
Output is correct |
| 32 |
Correct |
5 ms |
376 KB |
Output is correct |
| 33 |
Correct |
5 ms |
376 KB |
Output is correct |
| 34 |
Correct |
5 ms |
376 KB |
Output is correct |
| 35 |
Correct |
5 ms |
376 KB |
Output is correct |
| 36 |
Correct |
35 ms |
2764 KB |
Output is correct |
| 37 |
Correct |
37 ms |
3008 KB |
Output is correct |
| 38 |
Correct |
36 ms |
3008 KB |
Output is correct |
| 39 |
Correct |
31 ms |
3008 KB |
Output is correct |
| 40 |
Correct |
22 ms |
3008 KB |
Output is correct |
| 41 |
Correct |
29 ms |
3008 KB |
Output is correct |
| 42 |
Correct |
38 ms |
3136 KB |
Output is correct |
| 43 |
Correct |
14 ms |
2168 KB |
Output is correct |
| 44 |
Correct |
15 ms |
2412 KB |
Output is correct |
| 45 |
Correct |
18 ms |
3004 KB |
Output is correct |
| 46 |
Correct |
19 ms |
3008 KB |
Output is correct |
| 47 |
Correct |
19 ms |
3008 KB |
Output is correct |
| 48 |
Correct |
19 ms |
3008 KB |
Output is correct |
| 49 |
Correct |
14 ms |
2176 KB |
Output is correct |
| 50 |
Correct |
19 ms |
3008 KB |
Output is correct |
| 51 |
Correct |
20 ms |
3012 KB |
Output is correct |
| 52 |
Correct |
11 ms |
3048 KB |
Output is correct |
| 53 |
Correct |
11 ms |
3008 KB |
Output is correct |
| 54 |
Correct |
15 ms |
3008 KB |
Output is correct |
| 55 |
Correct |
11 ms |
3008 KB |
Output is correct |
| 56 |
Correct |
9 ms |
3008 KB |
Output is correct |
