제출 #1335863

#제출 시각아이디문제언어결과실행 시간메모리
1335863gohchingjaykJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
7 ms5552 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int INF = 1e18 + 5;
constexpr int MAXN = 200'000 + 5;
constexpr int MOD = 1e9 + 7;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	int N, K; cin >> N >> K;
	string S; cin >> S;
	
	vector<int> jindices;
	vector<int> oindices;
	vector<int> iindices;
	
	for (int i = 0; i < N; ++i) {
		if (S[i] == 'J') {
			jindices.emplace_back(i);
		}
		else if (S[i] == 'O') oindices.emplace_back(i);
		else iindices.emplace_back(i);
	}
	
	vector<int> dpJ(N, INF);
	for (int i = K-1; i < (int)jindices.size(); ++i) {
		int last = jindices[i-(K-1)];
		int curr = jindices[i];
		
		int rem = (curr - last + 1) - K;
		dpJ[curr] = rem;
	}
	
	int ptr = -1;
	
	vector<int> dpO(N, INF);
	int opt = INF;
	for (int i = K-1; i < (int)oindices.size(); ++i) {
		int last = oindices[i-(K-1)];
		int curr = oindices[i];
		
		while (ptr + 1 < (int)jindices.size() && jindices[ptr + 1] < last) {
			ptr++;
			opt = min(opt, dpJ[jindices[ptr]] - (jindices[ptr] + 1));
		}
		
		dpO[curr] = min(INF, (curr - last + 1) - K + last-1 + opt + 1);
	}
	
	ptr = -1;
	opt = INF;
	int ans = INF;
	for (int i = K-1; i < (int)iindices.size(); ++i) {
		int last = iindices[i-(K-1)];
		int curr = iindices[i];
		
		while (ptr + 1 < (int)oindices.size() && oindices[ptr + 1] < last) {
			ptr++;
			opt = min(opt, dpO[oindices[ptr]] - (oindices[ptr] + 1));
		}
		
		ans = min(ans, (curr - last + 1) - K + last-1 + opt + 1);
	}
	
	cout << (ans == INF ? -1ll : ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...