제출 #753874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753874		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	27 ms	3308 KiB

ho_t2

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second

using namespace std;

const ll N = 2e6 + 7;
const ll inf = 1e9;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

void be(){
    ios_base::sync_with_stdio (0);
    cin.tie (0);
//	freopen("herding.in","r",stdin);
//	freopen("herding.out","w",stdout);
}

void solve (){
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	vector <int> a(n), b(n), c(n);
	for (int i = 0; i < n; ++i){
		if (i) a[i] = a[i - 1], b[i] = b[i - 1], c[i] = c[i - 1];
		if (s[i] == 'J') ++a[i];
		if (s[i] == 'O') ++b[i];
		if (s[i] == 'I') ++c[i];
	}
	int mn = inf;
//	for (int i = 0; i < n; ++i) cout << a[i] << ' ';
//	cout << '\n';
//	for (int i = 0; i < n; ++i) cout << b[i] << ' ';
//	cout << '\n';
//	for (int i = 0; i < n; ++i) cout << c[i] << ' ';
//	cout << '\n';
	bool ok = 0;
	int pos1, pos2, pos3;
	pos1 = lower_bound (a.begin (), a.end (), k) - a.begin ();
	if (pos1 == n) ok = 1;
	if (!ok) pos2 = lower_bound (b.begin () + pos1, b.end (), k + b[pos1]) - b.begin ();
	if (pos2 == n) ok = 1;
	if (!ok) pos3 = lower_bound (c.begin () + pos2, c.end (), k + c[pos2]) - c.begin ();
	if (pos3 == n) ok = 1;
//	cout << pos1 << ' ' << pos2 << ' ' << pos3 << '\n';
	if (!ok) mn = min (mn, (pos3 + 1 - 3 * k));
	for (int i = 1; i < n; ++i){
		pos1 = lower_bound (a.begin () + i, a.end (), k + a[i - 1]) - a.begin ();
		if (pos1 == n) break;
		pos2 = lower_bound (b.begin () + pos1, b.end (), k + b[pos1]) - b.begin ();
		if (pos2 == n) break;
		pos3 = lower_bound (c.begin () + pos2, c.end (), k + c[pos2]) - c.begin ();
		if (pos3 == n) break;
 		mn = min (mn, (pos3 - i - 3 * k + 1));
//		cout << i << ' ' << pos1 << ' ' << pos2 << ' ' << pos3 << '\n';
	}
	if (mn == inf) mn = -1;
	cout << mn;
}

main (){
	be ();
	ll tt = 1;
//	cin >> tt;
	for (ll i = 1; i <= tt; ++i){
//		cout << "Case " << i << ':';
		solve ();
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t2.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main (){
      | ^~~~

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