Submission #953726

#	Time	Username	Problem	Language	Result	Execution time	Memory
953726		Angus_Yeung	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	7516 KiB

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 (stderr)

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 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87