Submission #988764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
988764	2024-05-26T01:13:16 Z	pcc	Bajka (COCI20_bajka)	C++17	70 / 70	49 ms	1316 KB

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

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1112 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	1116 KB	Output is correct
2	Correct	30 ms	1116 KB	Output is correct
3	Correct	30 ms	1116 KB	Output is correct
4	Correct	30 ms	1316 KB	Output is correct
5	Correct	25 ms	1116 KB	Output is correct
6	Correct	26 ms	1116 KB	Output is correct
7	Correct	38 ms	1116 KB	Output is correct
8	Correct	49 ms	1116 KB	Output is correct
9	Correct	49 ms	1116 KB	Output is correct
10	Correct	24 ms	1116 KB	Output is correct
11	Correct	37 ms	1296 KB	Output is correct