Submission #583846

#	Time	Username	Problem	Language	Result	Execution time	Memory
583846		MODDI	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	0 ms	212 KiB

ho_t2

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, k;
string str;
int main(){
	cin>>n>>k>>str;
	string cpy;
	int l = 0, r = n-1;
	while(str[l] == 'O' || str[l] == 'I')
		l++;
	while(str[r] == 'J' || str[r] == 'O')
		r--;
	if(l > r)
	{
		cout<<-1<<endl;
		return 0;
	}
	for(int i = l; i <= r; i++)
		cpy.pb(str[i]);
		
	str = cpy;
	int rez = 0, j = 0;
	string target;
	for(int i = 0; i < k; i++)
		target.pb('J');
	for(int i = 0; i < k; i++)
		target.pb('O');
	for(int i = 0; i < k; i++)
		target.pb('I');
	int dp[str.size()+1][target.size()+1];
	for(int i = 0; i <= str.size(); i++)
	{
		for(int j = 0; j <= target.size(); j++){
			if(i == 0 || j == 0)
				dp[i][j] = 0;
			else if(str[i-1] == target[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	cout<<str.size() - dp[str.size()][target.size()]<<endl;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i = 0; i <= str.size(); i++)
      |                 ~~^~~~~~~~~~~~~
ho_t2.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j = 0; j <= target.size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~
ho_t2.cpp:29:6: warning: unused variable 'rez' [-Wunused-variable]
   29 |  int rez = 0, j = 0;
      |      ^~~
ho_t2.cpp:29:15: warning: unused variable 'j' [-Wunused-variable]
   29 |  int rez = 0, j = 0;
      |               ^

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