oj.uz

Submission #447799

# Submission time Handle Problem Language Result Execution time Memory
447799 2021-07-27T14:46:46 Z Apiram Bajka (COCI20_bajka) C++14
20 / 70
 24 ms 1452 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){
	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

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

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