답안 #922811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922811	2024-02-06T06:54:36 Z	dimashhh	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	2000 ms	3632 KB

ho_t2

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 12, MOD = 1e9 + 7;

typedef long long ll;

int n,k,A[N],B[N],C[N];
string s;
vector<int> a,b,c;
void test(){
    cin >> n >> k >> s;
    s = "#" + s;
    for(int i = 1;i <= n;i++){
        A[i] = A[i - 1];
        B[i] = B[i - 1];
        C[i] = C[i - 1];
        if(s[i] == 'J'){
            A[i]++;
            a.push_back(i);
        }else if(s[i] == 'O'){
            B[i]++;
            b.push_back(i);
        }else{
            C[i]++;
            c.push_back(i);
        }
    }
    if(min({(int)a.size(),(int)b.size(),(int)c.size()}) < k){
        cout << -1 << '\n';
        return;
    }
    int res = 1e9;
    for(int i = 0;i < (int)a.size();i++){
        if(i + k - 1 >= (int)a.size()) break;
        int l = -1,r = c.size() - k;
        while(r - l > 1){
            int j = (l + r) >> 1;
            if(i + k - 1 < (int)a.size() && B[c[j]] - B[a[i + k - 1]] >= k){
                res = min(res,n - k * 3 - (a[i] - 1) - (n - c[j + k - 1]));
                r = j;
            }else{
                l = j;
            }
        }
        for(int j = (int)c.size() - k;j >= 0;j--){
            if(B[c[j]] - B[a[i + k - 1]] >= k){
                res = min(res,n - k * 3 - (a[i] - 1) - (n - c[j + k - 1]));
            }
        }
    }
    if(res == 1e9) res = -1;
    cout<< res << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T = 1;
//    cin >> T;
    while (T--)
        test();
}

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	2 ms	348 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	2 ms	348 KB	Output is correct
34	Correct	1 ms	344 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct

Subtask #3

0 / 87.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	2 ms	348 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	2 ms	348 KB	Output is correct
34	Correct	1 ms	344 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Execution timed out	2055 ms	3632 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-