Submission #957292

#	Time	Username	Problem	Language	Result	Execution time	Memory
957292		aaron_dcoder	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	12 ms	3388 KiB

ho_t2

#define NDEBUG


#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

int main()
{
	ll N,K;
	cin >> N >> K;

	string S;
	cin >> S;

	vector<ll> Js;
	vector<ll> Os;
	vector<ll> Is;

	for (ll i = 0; i < N; ++i)
	{
		if (S[i]=='J')
		{
			Js.push_back(i);
		}
		else if (S[i]=='O')
		{
			Os.push_back(i);
		}
		else
		{
			assert(S[i]=='I');
			Is.push_back(i);
		}
	}

	ll outp=INFTY;

	for (ll i = 0; i+K <= ll(Js.size()); ++i)
	{
		ll jidx = i+K-1;

		ll oidx = lower_bound(Os.cbegin(),Os.cend(), Js[jidx])-Os.cbegin()+K-1;
		if (ll(Os.size())<=oidx) break;
		ll iidx = lower_bound(Is.cbegin(), Is.cend(), Os[oidx])-Is.cbegin()+K-1;
		if (ll(Is.size())<=iidx) break;

		outp = min(outp,Is[iidx]-Js[i]+1);
	}

	cout << ((outp==INFTY)?-1:(outp-3*K)) << "\n";
}

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