oj.uz

Submission #988762

# Submission time Handle Problem Language Result Execution time Memory
988762 2024-05-26T01:08:03 Z pcc Bajka (COCI20_bajka) C++17
50 / 70
 51 ms 1368 KB 
#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);
	}
	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:30: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]
   30 |   for(int j = 1;j<i.size();j++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1308 KB Output is correct
2 Correct 30 ms 1112 KB Output is correct
3 Correct 30 ms 1112 KB Output is correct
4 Correct 31 ms 1116 KB Output is correct
5 Correct 25 ms 1112 KB Output is correct
6 Correct 25 ms 1316 KB Output is correct
7 Correct 39 ms 1116 KB Output is correct
8 Correct 49 ms 1368 KB Output is correct
9 Correct 51 ms 1368 KB Output is correct
10 Correct 24 ms 1116 KB Output is correct
11 Correct 37 ms 1116 KB Output is correct