oj.uz

Submission #244238

# Submission time Handle Problem Language Result Execution time Memory
244238 2020-07-03T09:07:02 Z WhipppedCream JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 10 ms 2552 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", &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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 9 ms 2084 KB Output is correct
37 Correct 10 ms 2444 KB Output is correct
38 Correct 10 ms 2340 KB Output is correct
39 Correct 9 ms 2452 KB Output is correct
40 Correct 9 ms 2440 KB Output is correct
41 Correct 9 ms 2428 KB Output is correct
42 Correct 10 ms 2444 KB Output is correct
43 Correct 7 ms 1472 KB Output is correct
44 Correct 8 ms 1832 KB Output is correct
45 Correct 9 ms 2364 KB Output is correct
46 Correct 9 ms 2448 KB Output is correct
47 Correct 9 ms 2364 KB Output is correct
48 Correct 9 ms 2428 KB Output is correct
49 Correct 8 ms 1576 KB Output is correct
50 Correct 10 ms 2428 KB Output is correct
51 Correct 10 ms 2448 KB Output is correct
52 Correct 8 ms 2172 KB Output is correct
53 Correct 9 ms 2428 KB Output is correct
54 Correct 9 ms 2552 KB Output is correct
55 Correct 8 ms 2552 KB Output is correct
56 Correct 8 ms 2552 KB Output is correct