Submission #953726

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953726	2024-03-26T14:43:28 Z	Angus_Yeung	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	7516 KB

ho_t2

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

ll n, k, ans;
ll dp[5][200010];
char a[200010];
deque<ll> q;

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	dp[1][0] = dp[2][0] = dp[3][0] = INF;
	
	for (int j = 1; j <= 3; j++) {
		while (!q.empty()) q.pop_back();
		for (int i = 1; i <= n; i++) {
			if (j == 1 && a[i] == 'J') q.push_back(i);
			if (j == 2 && a[i] == 'O') q.push_back(i);
			if (j == 3 && a[i] == 'I') q.push_back(i);
			while (q.size() > k) q.pop_front();
			if (q.size() < k) dp[j][i] = INF;
			else dp[j][i] = dp[j-1][q.front()-1]+(i-q.front()+1-k);
		}
	}
	
	ans = INF;
	for (int i = 0; i <= n; i++) ans = min(ans, dp[3][i]);
	
	if (ans == INF) cout << "-1\n";
	else cout << ans << "\n";
	
	return 0;
}
/*



*/

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:30:20: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   30 |    while (q.size() > k) q.pop_front();
      |           ~~~~~~~~~^~~
ho_t2.cpp:31:17: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   31 |    if (q.size() < k) dp[j][i] = INF;
      |        ~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
87.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	2 ms	6492 KB	Output is correct
3	Correct	1 ms	6488 KB	Output is correct
4	Correct	2 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6608 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6488 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6608 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	3 ms	6492 KB	Output is correct
18	Correct	2 ms	6612 KB	Output is correct
19	Correct	1 ms	6488 KB	Output is correct
20	Correct	1 ms	6488 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	1 ms	6492 KB	Output is correct
23	Correct	1 ms	6488 KB	Output is correct
24	Correct	1 ms	6492 KB	Output is correct
25	Correct	1 ms	6492 KB	Output is correct
26	Correct	1 ms	6628 KB	Output is correct
27	Correct	1 ms	6492 KB	Output is correct
28	Correct	2 ms	6492 KB	Output is correct
29	Correct	1 ms	6492 KB	Output is correct
30	Correct	1 ms	6492 KB	Output is correct
31	Correct	1 ms	6488 KB	Output is correct
32	Correct	1 ms	6552 KB	Output is correct
33	Correct	1 ms	6492 KB	Output is correct
34	Correct	1 ms	6492 KB	Output is correct
35	Correct	1 ms	6500 KB	Output is correct
36	Correct	8 ms	6748 KB	Output is correct
37	Correct	7 ms	7008 KB	Output is correct
38	Correct	7 ms	7192 KB	Output is correct
39	Correct	7 ms	7004 KB	Output is correct
40	Correct	10 ms	7260 KB	Output is correct
41	Correct	7 ms	7004 KB	Output is correct
42	Correct	8 ms	7004 KB	Output is correct
43	Correct	7 ms	6876 KB	Output is correct
44	Correct	6 ms	7004 KB	Output is correct
45	Correct	7 ms	7260 KB	Output is correct
46	Correct	7 ms	7260 KB	Output is correct
47	Correct	7 ms	7256 KB	Output is correct
48	Correct	8 ms	7260 KB	Output is correct
49	Correct	5 ms	6760 KB	Output is correct
50	Correct	7 ms	7256 KB	Output is correct
51	Correct	7 ms	7260 KB	Output is correct
52	Correct	7 ms	7516 KB	Output is correct
53	Correct	7 ms	7516 KB	Output is correct
54	Correct	6 ms	6912 KB	Output is correct
55	Correct	7 ms	7260 KB	Output is correct
56	Correct	6 ms	7516 KB	Output is correct

Submission #953726

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 12.0 / 12.0

Subtask #3 87.0 / 87.0

Subtask #1
1.0 / 1.0

Subtask #2
12.0 / 12.0

Subtask #3
87.0 / 87.0