Submission #988764

#	Time	Username	Problem	Language	Result	Execution time	Memory
988764		pcc	Bajka (COCI20_bajka)	C++17	70 / 70	49 ms	1316 KiB

bajka

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll


const int mxn = 330;
int N,M;
int dist[mxn][mxn];
int dp[mxn];

string s,t;
vector<int> pos[26];

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	cin>>s>>t;
	for(int i = 0;i<N;i++){
		pos[s[i]-'a'].push_back(i);
	}
	if(N == 1&&s == t){
		cout<<"0\n";
		return 0;
	}
	else if(N == 1){
		cout<<"-1\n";
		return 0;
	}
	for(auto &i:dist)for(auto &j:i)j = 1e9;
	for(auto &i:pos){
		for(int j = 1;j<i.size();j++){
			dist[i[j]][i[j-1]] = i[j]-i[j-1];
			dist[i[j-1]][i[j]] = i[j]-i[j-1];
		}
	}
	for(int i = 0;i<N;i++)dist[i][i] = 0;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			for(int k = 0;k<N;k++){
				dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k]);
			}
		}
	}
	int dp2[mxn];
	for(auto &tar:t){
		fill(dp2,dp2+mxn,(int)1e9);
		for(auto &j:pos[tar-'a']){
			for(int k = 0;k<N;k++){
				if(j)dp2[j] = min(dp2[j],dp[k]+dist[k][j-1]+1);
				if(j+1<N)dp2[j] = min(dp2[j],dp[k]+dist[k][j+1]+1);
			}
		}
		copy(dp2,dp2+N,dp);
	}
	int ans = *min_element(dp,dp+N);
	if(ans>=(int)1e9)cout<<-1;
	else cout<<ans-1;
}

Compilation message (stderr)

bajka.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~
bajka.cpp: In function 'int main()':
bajka.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int j = 1;j<i.size();j++){
      |                 ~^~~~~~~~~

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