제출 #1325901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325901		tkm_algorithms	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	12 ms	12476 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9;

int f(char c) {
	if (c == 'J')return 0;
	if (c == 'O')return 1;
	return 2;
}

void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	
	int p[n][3], sf[n+1][3];
	memset(p, 0, sizeof p);
	memset(sf, 0, sizeof sf);

	vector<int> g[3];
	rep(i, 0, n)
		g[f(s[i])].push_back(i);

	rep(i, 0, n) {
		p[i][f(s[i])] += 1;
		if (i)rep(j, 0, 3)p[i][j] += p[i-1][j];
	}
	
	for (int i = n-1; i >= 0; --i) {
		sf[i][f(s[i])] += 1;
		if (i < n-1)rep(j, 0, 3)sf[i][j] += sf[i+1][j];
	}
	
	int last = 0, ok= 1, res = inf;
	if (sz(g[0]) < k)last = n-1, ok = 0;
	else last = g[0][k-1];
	
	rep(j, 1, 3) {
		if (sz(g[j]) < p[last][j]+k){ok = 0;break;}
		last = g[j][p[last][j]+k-1];
	}
	
	if (ok)res = last+1-3*k;

	rep(i, 0, n) { // ilki i sany ayyryan.
		ok = true;
		rep(j, 0, 3)
			ok &= (p[i][j] <= sf[0][j]-k);
		if (!ok)break;
		last = i, ok = 1;
		rep(j, 0, 3) {
			if (sz(g[j]) < p[last][j]+k){ok = 0; break;}
			last = g[j][p[last][j]+k-1];
		}
		
		if (ok)res = min(res, last-i-3*k);
	}
	if (res == inf)res = -1;
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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