Submission #447804

#	Time	Username	Problem	Language	Result	Execution time	Memory
447804		Apiram	Bajka (COCI20_bajka)	C++14	70 / 70	917 ms	1568 KiB

bajka

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>dp(500,vector<int>(500,-1));
vector<vector<int>>freq(26);
int64_t solve(int i,int cur,string t,string s){
	if (i==t.length())return 0;
	if (dp[i][cur]!=-1){
		return dp[i][cur];
	}
	int64_t counts=INT_MAX;
	for (auto x:freq[t[i-1]-'a']){
		if (x-1>=0&&s[x-1]==t[i])
		counts=min(counts,solve(i+1,x-1,t,s)+(int64_t)abs(cur-x) + 1);
		if (x+1<s.length()&&s[x+1]==t[i]){
			counts=min(counts,solve(i+1,x+1,t,s)+(int64_t)abs(cur - x) + 1);
		}
	}
	return dp[i][cur]=counts;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
string s;
cin>>s;
string t;cin>>t;

for (int i = 0 ;i<n;++i){
	freq[s[i]-'a'].push_back(i);
}
int64_t counts=INT_MAX;
for (auto x:freq[t[0]-'a']){
	counts=min(counts,solve(1,x,t,s));
}
if (counts==INT_MAX)cout<<-1<<endl;
else
cout<<counts<<endl;

return 0;}

Compilation message (stderr)

bajka.cpp: In function 'int64_t solve(int, int, std::string, std::string)':
bajka.cpp:6:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |  if (i==t.length())return 0;
      |      ~^~~~~~~~~~~~
bajka.cpp:14:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   if (x+1<s.length()&&s[x+1]==t[i]){
      |       ~~~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50