답안 #842282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842282	2023-09-02T17:14:41 Z	dong_liu	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	6 ms	3304 KB

ho_t2

#include "bits/stdc++.h"
using namespace std;

const int N=2e5;
const string JOI="JOI";

int n,k;
string s;
int jmp[3][N+1];

int solve(int i) {
	i=jmp[0][i];
	i=jmp[1][i];
	i=jmp[2][i];
	return i==n?-1:i;
}

int main() {
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	cin>>n>>k>>s;
	for(int x=0;x<3;x++){
		jmp[x][n]=n;
		for(int i=0,j=0,c=0;i<n;i++){
			while(j<n&&c<k)c+=s[j++]==JOI[x];
			jmp[x][i]=c==k?j-1:n;
			c-=s[i]==JOI[x];
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		int j=solve(i);
		if(j!=-1)ans=min(ans,j-i+1-k*3);
	}
	cout<<(ans==n?-1:ans)<<'\n';
}

Subtask #1

1.0 / 1.0

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

Subtask #2

12.0 / 12.0

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

Subtask #3

87.0 / 87.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2508 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	0 ms	2512 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	1 ms	2648 KB	Output is correct
14	Correct	0 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	0 ms	2396 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	0 ms	2396 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	2396 KB	Output is correct
27	Correct	1 ms	2396 KB	Output is correct
28	Correct	1 ms	2396 KB	Output is correct
29	Correct	1 ms	2396 KB	Output is correct
30	Correct	1 ms	2396 KB	Output is correct
31	Correct	1 ms	2396 KB	Output is correct
32	Correct	1 ms	2396 KB	Output is correct
33	Correct	1 ms	2396 KB	Output is correct
34	Correct	0 ms	2396 KB	Output is correct
35	Correct	0 ms	2396 KB	Output is correct
36	Correct	5 ms	3048 KB	Output is correct
37	Correct	5 ms	3304 KB	Output is correct
38	Correct	5 ms	3216 KB	Output is correct
39	Correct	6 ms	3296 KB	Output is correct
40	Correct	5 ms	3156 KB	Output is correct
41	Correct	5 ms	3304 KB	Output is correct
42	Correct	6 ms	3304 KB	Output is correct
43	Correct	3 ms	3052 KB	Output is correct
44	Correct	4 ms	3048 KB	Output is correct
45	Correct	5 ms	3304 KB	Output is correct
46	Correct	5 ms	3168 KB	Output is correct
47	Correct	4 ms	3304 KB	Output is correct
48	Correct	4 ms	3304 KB	Output is correct
49	Correct	3 ms	2996 KB	Output is correct
50	Correct	5 ms	3304 KB	Output is correct
51	Correct	4 ms	3304 KB	Output is correct
52	Correct	3 ms	3048 KB	Output is correct
53	Correct	3 ms	3304 KB	Output is correct
54	Correct	2 ms	3304 KB	Output is correct
55	Correct	2 ms	3180 KB	Output is correct
56	Correct	2 ms	3304 KB	Output is correct