제출 #753874

#제출 시각아이디문제언어결과실행 시간메모리
753874vjudge1JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
27 ms3308 KiB
#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 (){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...