oj.uz

Submission #447804

# Submission time Handle Problem Language Result Execution time Memory
447804 2021-07-27T14:50:28 Z Apiram Bajka (COCI20_bajka) C++14
70 / 70
 917 ms 1568 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 47 ms 1556 KB Output is correct
8 Correct 557 ms 1540 KB Output is correct
9 Correct 917 ms 1556 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 21 ms 1568 KB Output is correct