oj.uz

답안 #861189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861189 2023-10-15T15:26:44 Z dsyz JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 9 ms 5860 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	string s;
	cin>>s;
	ll Opsum[N];
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		if(s[i] == 'O'){
			cur++;
		}
		Opsum[i] = cur;
	}
	ll Jpre[N];
	cur = 0;
	ll ptr = 0;
	for(ll r = 0;r < N;r++){
		if(s[r] == 'J'){
			cur++;
		}
		while(ptr < r && (cur > K || s[ptr] != 'J')){
			if(s[ptr] == 'J') cur--;
			ptr++;
		}
		if(cur >= K) Jpre[r] = ptr;
		else Jpre[r] = -1;
	}
	
	ll Isuf[N];
	cur = 0;
	ptr = N - 1;
	for(ll l = N - 1;l >= 0;l--){
		if(s[l] == 'I'){
			cur++;
		}
		while(ptr > l && (cur > K || s[ptr] != 'I')){
			if(s[ptr] == 'I') cur--;
			ptr--;
		}
		if(cur >= K) Isuf[l] = ptr;
		else Isuf[l] = -1;
	}
	
	ll L = 1;
	ll R = 1;
	bool ok = 0;
	ll ans = 1e18;
	while(R < N - 1){
		while(L < R && Opsum[R] - Opsum[L] >= K){
			L++;
		}
		if(Jpre[L - 1] != -1 && Isuf[R + 1] != -1 && Opsum[R] - Opsum[L - 1] >= K){
			ok = 1;
			ans = min(ans,(Isuf[R + 1] - Jpre[L - 1] + 1) - 3 * K);
		}
		R++;
	}
	if(!ok){
		cout<<-1<<'\n';
	}else{
		cout<<ans<<'\n';
	}
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 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 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 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 0 ms 348 KB Output is correct
2 Correct 0 ms 452 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 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 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 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 456 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct

Subtask #3
87.0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 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 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 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 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 456 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 6 ms 5096 KB Output is correct
37 Correct 6 ms 5600 KB Output is correct
38 Correct 6 ms 5608 KB Output is correct
39 Correct 7 ms 5608 KB Output is correct
40 Correct 7 ms 5608 KB Output is correct
41 Correct 7 ms 5608 KB Output is correct
42 Correct 9 ms 5848 KB Output is correct
43 Correct 5 ms 3672 KB Output is correct
44 Correct 5 ms 4292 KB Output is correct
45 Correct 7 ms 5672 KB Output is correct
46 Correct 6 ms 5608 KB Output is correct
47 Correct 6 ms 5604 KB Output is correct
48 Correct 6 ms 5608 KB Output is correct
49 Correct 4 ms 3816 KB Output is correct
50 Correct 7 ms 5596 KB Output is correct
51 Correct 6 ms 5608 KB Output is correct
52 Correct 4 ms 5340 KB Output is correct
53 Correct 4 ms 5860 KB Output is correct
54 Correct 4 ms 5608 KB Output is correct
55 Correct 5 ms 5604 KB Output is correct
56 Correct 4 ms 5472 KB Output is correct