oj.uz

Submission #244237

# Submission time Handle Problem Language Result Execution time Memory
244237 2020-07-03T08:41:16 Z WhipppedCream JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 5 ms 384 KB 
#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", &n, &k);
	scanf("%s", 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(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

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", &n, &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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -