Submission #674950

#	Time	Username	Problem	Language	Result	Execution time	Memory
674950		sudheerays123	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	27 ms	70872 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 3000+5 , INF = 1e18 , MOD = 1e9+7;

ll n,k;
string s,u = " ";
ll dp[N][N];

ll go(ll i , ll j){
	if(i == n+1 && j == (3*k)+1) return 0;
	if(i > n+1 || j > (3*k)+1) return INF;

	if(dp[i][j] != -1) return dp[i][j];

	ll ans = INF;

	if(s[i] == u[j]) ans = min({ans,go(i+1,j+1),go(i+1,j)+((i == n || i == 1)?0:1)});
	else ans = min(ans,go(i+1,j)+((i == n || i == 1)?0:1));

	return dp[i][j] = ans;
}

void solve(){


	cin >> n >> k >> s;
	s = ' '+s;

	for(ll i = 1; i <= k; i++) u += 'J';
	for(ll i = 1; i <= k; i++) u += 'O';
	for(ll i = 1; i <= k; i++) u += 'I';

	memset(dp,-1,sizeof dp);

	ll ans = go(1,1);

	if(ans == INF) cout << "-1";
	else cout << ans;
}

int main(){

	fast;

	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();

	return 0;
}

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