oj.uz

답안 #255081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255081 2020-07-31T08:16:38 Z Goolakh JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 11 ms 3328 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math") 
 
#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e5+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,k,ans=inf;
string s;
vector<ll> vv[3];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>k>>s;
	for(int i=0;i<n;i++) vv[(s[i]=='J' ? 0:(s[i]=='O' ? 1:2))].pb(i);
	ll i[3]={0,0,0};
	for(;i[0]<SZ(vv[0]);i[0]++){
		bool F=0;
		for(int j:{1,2}){
			if(i[j-1]+k-1>=SZ(vv[j-1])){F=1;break;}
			while(i[j]<SZ(vv[j]) && vv[j][i[j]]<vv[j-1][i[j-1]+k-1]) i[j]++;
		}
		if(i[2]+k-1>=SZ(vv[2])) F=1;
		if(F) break;
		//cout<<i[0]<<' '<<i[1]<<' '<<i[2]<<endl;
		ans=min(ans,vv[2][i[2]+k-1]-vv[0][i[0]]+1-3*k);
	}
	cout<<(ans==inf ? -1:ans);
	
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
87.0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 0 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 6 ms 2452 KB Output is correct
37 Correct 9 ms 2996 KB Output is correct
38 Correct 7 ms 2992 KB Output is correct
39 Correct 6 ms 2936 KB Output is correct
40 Correct 6 ms 2936 KB Output is correct
41 Correct 6 ms 3064 KB Output is correct
42 Correct 11 ms 2996 KB Output is correct
43 Correct 3 ms 1820 KB Output is correct
44 Correct 4 ms 2136 KB Output is correct
45 Correct 5 ms 3064 KB Output is correct
46 Correct 5 ms 2996 KB Output is correct
47 Correct 5 ms 2936 KB Output is correct
48 Correct 5 ms 2876 KB Output is correct
49 Correct 3 ms 1920 KB Output is correct
50 Correct 6 ms 2992 KB Output is correct
51 Correct 6 ms 3068 KB Output is correct
52 Correct 4 ms 2364 KB Output is correct
53 Correct 5 ms 2936 KB Output is correct
54 Correct 6 ms 3328 KB Output is correct
55 Correct 5 ms 3328 KB Output is correct
56 Correct 4 ms 3328 KB Output is correct