Submission #244238

#	Time	Username	Problem	Language	Result	Execution time	Memory
244238		WhipppedCream	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	2552 KiB

ho_t2

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef long long ll;

#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int md = 1e9+7;
const ll inf = 1e18;
const int maxn = 2e5+5;

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

int n, k;

vector<int> js;
vector<int> is;

char s[maxn];
int qs[maxn];

int main()
{
	scanf("%*d %d", &k);
	scanf("%s", s+1);
	n = strlen(s+1);
	for(int i = 1; i<= n; i++)
	{
		if(s[i] == 'J')
		{
			js.pb(i);
		}
		else if(s[i] == 'O')
		{
			qs[i] = 1;
		}
		else is.pb(i);
		qs[i] += qs[i-1];
	}
	int best = 1e9;
	int cur = 0;
	for(int j = k-1; j< (int) js.size(); j++)
	{
		while(cur+k-1< (int) is.size() && qs[is[cur]-1]-qs[js[j]]< k) cur++;
		if(cur+k-1< (int) is.size() && qs[is[cur]-1]-qs[js[j]]>= k)
		{
			best = min(best, is[cur+k-1]-js[j-k+1]+1);
		}
	}
	if(best == 1e9) printf("-1\n");
	else printf("%d\n", best-3*k);

}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%*d %d", &k);
  ~~~~~^~~~~~~~~~~~~~
ho_t2.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s+1);
  ~~~~~^~~~~~~~~~~

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