Submission #208437

#	Time	Username	Problem	Language	Result	Execution time	Memory
208437		cstuart	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	19 ms	2924 KiB

ho_t2

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007ll
#define EPS 1e-9

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, K, B;
vector <ll> VJ, VO, VI;
vector <ll>::iterator VJS, VJE, VOS, VOE, VIS, VIE;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K;
	for (ll i = 1; i <= N; i++) {
		char ch;
		cin >> ch;
		if (ch == 'J') VJ.push_back(i);
		else if (ch == 'O') VO.push_back(i);
		else VI.push_back(i);
	}
	
	B = 1000000;
	
	for (ll i = 0; i < (ll)VJ.size(); i++) {
		VJS = VJ.begin() + i;
		if (VJ.end() - VJS <= K - 1) continue;
		VJE = VJS + K - 1;
		VOS = upper_bound(VO.begin(), VO.end(), *VJE);
		if (VO.end() - VOS <= K - 1) continue;
		VOE = VOS + K - 1;
		VIS = upper_bound(VI.begin(), VI.end(), *VOE);
		if (VI.end() - VIS <= K - 1) continue;
		VIE = VIS + K - 1;
		ll C = N - (*VJS - 1) - (N - *VIE) - (3 * K);
		B = min(B, C);
	}
	
	if (B == 1000000) cout << -1;
	else cout << B;
		
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87