oj.uz

Submission #369295

# Submission time Handle Problem Language Result Execution time Memory
369295 2021-02-21T07:16:31 Z phathnv JJOOII 2 (JOI20_ho_t2) C++11
100 / 100
 10 ms 3276 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 1;
const char c[3] = {'J', 'O', 'I'};

int n, k, cnt[N][3];
string s;

void ReadInput(){
    cin >> n >> k;
    cin >> s;
    s = '*' + s;
}

void Solve(){
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < 3; j++)
            cnt[i][j] = cnt[i - 1][j] + (s[i] == c[j]);

    int res = 1e9;
    int ptr[4] = {1, 1, 1, 1};
    for(ptr[0] = 0; ptr[0] < n; ptr[0]++){
        for(int j = 1; j <= 3; j++)
            while (ptr[j] < n && cnt[ptr[j]][j - 1] - cnt[ptr[j - 1]][j - 1] < k)
                ptr[j]++;
        if (cnt[ptr[3]][2] - cnt[ptr[2]][2] >= k)
            res = min(res, (ptr[3] - ptr[0]) - 3 * k);
    }
    cout << (res == 1e9? -1 : res);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 400 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 400 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 400 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 7 ms 3008 KB Output is correct
37 Correct 10 ms 3252 KB Output is correct
38 Correct 8 ms 3272 KB Output is correct
39 Correct 8 ms 3124 KB Output is correct
40 Correct 7 ms 3252 KB Output is correct
41 Correct 7 ms 3252 KB Output is correct
42 Correct 8 ms 3252 KB Output is correct
43 Correct 4 ms 2284 KB Output is correct
44 Correct 6 ms 2528 KB Output is correct
45 Correct 6 ms 3252 KB Output is correct
46 Correct 7 ms 3252 KB Output is correct
47 Correct 6 ms 3252 KB Output is correct
48 Correct 6 ms 3252 KB Output is correct
49 Correct 4 ms 2164 KB Output is correct
50 Correct 6 ms 3276 KB Output is correct
51 Correct 7 ms 3252 KB Output is correct
52 Correct 5 ms 3132 KB Output is correct
53 Correct 5 ms 3272 KB Output is correct
54 Correct 5 ms 3252 KB Output is correct
55 Correct 5 ms 3252 KB Output is correct
56 Correct 5 ms 3252 KB Output is correct