Submission #1322294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322294		aaaaaaaa	JJOOII 2 (JOI20_ho_t2)	C++20	1 / 100	1 ms	332 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;


#define int long long

const int inf = 5e18;

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;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87