oj.uz

Submission #244874

# Submission time Handle Problem Language Result Execution time Memory
244874 2020-07-05T07:59:33 Z maximath_1 JJOOII 2 (JOI20_ho_t2) C++11
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int cnt[3][200005], last[3][200005], n, k;
string s;

void proc(int id){
	int lf = 0;
	for(int rg = 1; rg <= n; rg ++){
		while(cnt[id][rg] - cnt[id][lf] >= k) lf ++;
		last[id][rg - 1] = lf - 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	cin >> s;
	for(int i = 0; i < n; i ++){
		if(s[i] == 'J') cnt[0][i + 1]++;
		if(s[i] == 'O') cnt[1][i + 1]++;
		if(s[i] == 'I') cnt[2][i + 1]++;
	}

	for(int i = 1; i <= n; i ++) for(int j = 0; j < 3; j ++)
		cnt[j][i] += cnt[j][i - 1];

	for(int i = 0; i < 3; i ++) proc(i);

	int ans = 2000000000;

	for(int i = 0; i < n; i ++){
		int nw = last[2][i];
		nw --;
		if(nw >= 0) nw = last[1][nw];
		else nw = -1000000;
		nw --;
		if(nw >= 0) nw = last[0][nw];
		else nw = -1000000;

		if(nw != -1000000)
			ans = min(ans, i - nw + 1 - 3 * k);
	}

	if(ans == 2000000000) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -