oj.uz

Submission #352629

# Submission time Handle Problem Language Result Execution time Memory
352629 2021-01-21T03:17:30 Z mariowong JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define pbb pair<bool,bool>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xmod (ll)(1e9+7) 
#define hmod 1286031825167LL
using namespace std;

int n,k,len,pt1,pt2,sum,ans;
string s;
vector <int> pos[5];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> s; len=s.length();
	for (int i=0;i<len;i++){
		if (s[i] == 'J')
		pos[0].pb(i);
		if (s[i] == 'O')
		pos[1].pb(i);
		if (s[i] == 'I')
		pos[2].pb(i);
	}
	ans=1e9;
	if (k-1 > (int)pos[1].size()-1 && k-1 > (int)pos[2].size()-1 && k-1 > (int)pos[0].size()-1){
		cout << "-1\n";
		return 0;
	}
	for (int i=1;i<=k-1;i++){
		sum+=pos[0][i]-pos[0][i-1]-1;
		sum+=pos[1][i]-pos[1][i-1]-1;
		sum+=pos[2][i]-pos[2][i-1]-1;
	}
	pt1=k-1; pt2=k-1;
	for (int i=k-1;i<(int)pos[0].size();i++){
		while (pt1 < (int)pos[1].size() && pos[1][pt1-(k-1)] < pos[0][i]){
			sum-=(pos[1][pt1-(k-2)]-pos[1][pt1-(k-1)]-1);
			pt1++;
			if (pt1 == (int)pos[1].size())
			goto out;
			sum+=(pos[1][pt1]-pos[1][pt1-1]-1);
		} 
		while (pt2 < (int)pos[2].size() && pos[2][pt2-(k-1)] < pos[1][pt1]){
			sum-=(pos[2][pt2-(k-2)]-pos[2][pt2-(k-1)]-1);
			pt2++;
			if (pt2 == (int)pos[2].size())
			goto out;
			sum+=(pos[2][pt2]-pos[2][pt2-1]-1);
		}
		ans=min(ans,sum+pos[1][pt1-(k-1)]-pos[0][i]-1+pos[2][pt2-(k-1)]-pos[1][pt1]-1);
	}
	out:;
	if (ans == 1e9)
	cout << "-1\n";
	else
	cout << ans << "\n";
    return 0;	
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -