Submission #1322300

#TimeUsernameProblemLanguageResultExecution timeMemory
1322300aaaaaaaaJJOOII 2 (JOI20_ho_t2)C++20
1 / 100
0 ms332 KiB
#include <bits/stdc++.h>
using namespace std;


#define int long long

const int inf = 1e9;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, k, ans = inf;
	string str;
	cin >> n >> k >> str;
	
	vector<int> dpje(n + 5, inf), dpof(n + 5, inf), dpoe(n + 5, inf), dpif(n + 5, inf);
	vector<char> pos[30];


	for(int i = 0; i < (int) str.size(); ++i){
		int key = str[i] - 'A';
		pos[key].push_back(i);
		if(str[i] == 'J'){
			if((int) pos[key].size() >= k){
				dpje[i] = i - pos[key][(int) pos[key].size() - k] + 1 - k;
			}
		}else if(str[i] == 'O'){
			if((int) pos['J' - 'A'].size()){
				if(i) dpof[i] = dpof[pos[key].back()] + i - pos[key].back();
				dpof[i] = min(dpof[i], dpje[pos['J' - 'A'].back()] + i - pos['J' - 'A'].back() - 1);
			}
			if((int) pos[key].size() >= k){
				if(i) dpoe[i] = dpoe[pos[key].back()] + i - pos[key].back();
				dpoe[i] = min(dpoe[i], dpof[pos[key][(int) pos[key].size() - k]] + i - pos[key][(int) pos[key].size() - k] + 1 - k);
			}
		//	cout << dpof[i] << " " << dpoe[i] << "\n";
		}else{
			if((int) pos['O' - 'A'].size()){
				if(i) dpif[i] = dpif[pos[key].back()] + i - pos[key].back();
				dpif[i] = min(dpif[i], dpoe[pos['O' - 'A'].back()] + i - pos['O' - 'A'].back() - 1);
			}
			if((int) pos[key].size() >= k){
				ans = min(ans, dpif[pos[key][(int) pos[key].size() - k]] + i - pos[key][(int) pos[key].size() - k] + 1 - k);
			}
		}
	}

	cout << (ans >= ((int) str.size()) ? -1 : ans) << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...