Submission #716204

#	Time	Username	Problem	Language	Result	Execution time	Memory
716204		shoryu386	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	15 ms	5348 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

#define int long long

main(){
	//given a string, find the shortest substring with K level JOI as a subsequence
	//two pointer?
	//but how delete
	
	//if we can compute the closest index in which we can find K 'J's, K 'O's, and K 'I's quickly, then
	
	
	int n, k; cin >> n >> k;
	string s; cin >> s;
	
	int l = 0, r = -1, jcount = 0;
	int jc[n], oc[n], ic[n];
	for (int x = 0; x < n; x++) jc[x] = LLONG_MAX/3, oc[x] = LLONG_MAX/3, ic[x] = LLONG_MAX/3;
	
	while (l != n-1){
		if (jcount >= k) jc[l] = min(jc[l], r);
		if (jcount >= k){
			if (s[l] == 'J') jcount--;
			l++;
		}
		else if (r != n){
			r++;
			if (r != n && s[r] == 'J') jcount++;
		}
		else break;
		if (jcount >= k) jc[l] = min(jc[l], r);
	}
	
	l = 0, r = -1, jcount = 0;
	while (l != n-1){
		if (jcount >= k) oc[l] = min(oc[l], r);
		if (jcount >= k){
			if (s[l] == 'O') jcount--;
			l++;
		}
		else if (r != n){
			r++;
			if (r != n && s[r] == 'O') jcount++;
		}
		else break;
		if (jcount >= k) oc[l] = min(oc[l], r);
	}
	
	l = 0, r = -1, jcount = 0;
	while (l != n-1){
		if (jcount >= k) ic[l] = min(ic[l], r);
		if (jcount >= k){
			if (s[l] == 'I') jcount--;
			l++;
		}
		else if (r != n){
			r++;
			if (r != n && s[r] == 'I') jcount++;
		}
		else break;
		if (jcount >= k) ic[l] = min(ic[l], r);
	}
	
	/*
	for (int x = 0; x < n; x++) cerr << jc[x] << ' ';
	cerr << '\n';
	for (int x = 0; x < n; x++) cerr << oc[x] << ' ';
	cerr << '\n';
	for (int x = 0; x < n; x++) cerr << ic[x] << ' ';
	cerr << '\n';
	*/
	int ans = LLONG_MAX/3;
	for (int x = 0; x < n; x++){
		int cur = jc[x];
		
		if (cur >= n) continue;
		
		cur = oc[cur];
		
		if (cur >= n) continue;
		
		cur = ic[cur];
		//cout << x << " " << cur << '\n';
		ans = min(cur - x + 1, ans);
		
	}
		
	if (ans > LLONG_MAX/5) cout << -1;
	else cout << ans - 3*k;
}

Compilation message (stderr)

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

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