oj.uz

Submission #352635

# Submission time Handle Problem Language Result Execution time Memory
352635 2021-01-21T03:25:50 Z mariowong JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 7 ms 2052 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define pbb pair<bool,bool>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xmod (ll)(1e9+7) 
#define hmod 1286031825167LL
using namespace std;

int n,k,len,pt1,pt2,sum,ans;
string s;
vector <int> pos[5];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> s; len=s.length();
	for (int i=0;i<len;i++){
		if (s[i] == 'J')
		pos[0].pb(i);
		if (s[i] == 'O')
		pos[1].pb(i);
		if (s[i] == 'I')
		pos[2].pb(i);
	}
	ans=1e9;
	if (k-1 > (int)pos[1].size()-1 && k-1 > (int)pos[2].size()-1 && k-1 > (int)pos[0].size()-1){
		cout << "-1\n";
		return 0;
	}
	for (int i=1;i<=k-1;i++){
		sum+=pos[0][i]-pos[0][i-1]-1;
		sum+=pos[1][i]-pos[1][i-1]-1;
		sum+=pos[2][i]-pos[2][i-1]-1;
	}
	pt1=k-1; pt2=k-1;
	for (int i=k-1;i<(int)pos[0].size();i++){
		while (pt1 < (int)pos[1].size() && pos[1][pt1-(k-1)] < pos[0][i]){
			sum-=(pos[1][pt1-(k-2)]-pos[1][pt1-(k-1)]-1);
			pt1++;
			if (pt1 == (int)pos[1].size())
			goto out;
			sum+=(pos[1][pt1]-pos[1][pt1-1]-1);
		} 
		while (pt2 < (int)pos[2].size() && pos[2][pt2-(k-1)] < pos[1][pt1]){
			sum-=(pos[2][pt2-(k-2)]-pos[2][pt2-(k-1)]-1);
			pt2++;
			if (pt2 == (int)pos[2].size())
			goto out;
			sum+=(pos[2][pt2]-pos[2][pt2-1]-1);
		}
		ans=min(ans,sum+pos[1][pt1-(k-1)]-pos[0][i]-1+pos[2][pt2-(k-1)]-pos[1][pt1]-1);
		sum-=(pos[0][i-(k-2)]-pos[0][i-(k-1)]-1);
		if (i < (int)pos[0].size()-1)
		sum+=(pos[0][i+1]-pos[0][i]-1);
	}
	out:;
	if (ans == 1e9)
	cout << "-1\n";
	else
	cout << ans << "\n";
    return 0;	
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 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 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 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 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 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 384 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 492 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 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 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 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 384 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 492 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 6 ms 1660 KB Output is correct
37 Correct 6 ms 1968 KB Output is correct
38 Correct 6 ms 1988 KB Output is correct
39 Correct 6 ms 2052 KB Output is correct
40 Correct 5 ms 2032 KB Output is correct
41 Correct 6 ms 1972 KB Output is correct
42 Correct 7 ms 1848 KB Output is correct
43 Correct 3 ms 1292 KB Output is correct
44 Correct 4 ms 1520 KB Output is correct
45 Correct 5 ms 2032 KB Output is correct
46 Correct 5 ms 2024 KB Output is correct
47 Correct 5 ms 2032 KB Output is correct
48 Correct 5 ms 2044 KB Output is correct
49 Correct 3 ms 1360 KB Output is correct
50 Correct 5 ms 2020 KB Output is correct
51 Correct 5 ms 2032 KB Output is correct
52 Correct 4 ms 1648 KB Output is correct
53 Correct 5 ms 1764 KB Output is correct
54 Correct 4 ms 2036 KB Output is correct
55 Correct 3 ms 2036 KB Output is correct
56 Correct 4 ms 2036 KB Output is correct