oj.uz

답안 #674950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674950 2022-12-26T16:42:51 Z sudheerays123 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 27 ms 70872 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 70872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 70872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 70872 KB Output isn't correct
2 Halted 0 ms 0 KB -