Submission #447799

#	Time	Username	Problem	Language	Result	Execution time	Memory
447799		Apiram	Bajka (COCI20_bajka)	C++14	20 / 70	24 ms	1452 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){
	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]-'a']){
		if (x!=cur)
		counts=min(counts,solve(i+1,x,t)+(int64_t)abs(cur-x));
	}
	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));
}
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)':
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;
      |      ~^~~~~~~~~~~~

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