oj.uz

Submission #589116

# Submission time Handle Problem Language Result Execution time Memory
589116 2022-07-04T09:28:53 Z Iwanttobreakfree Bajka (COCI20_bajka) C++
20 / 70
 1000 ms 692 KB 
#include <iostream>
#include <vector>
using namespace std;
void DP(int n,int m,int i,int j,vector<vector<int>>& dp,vector<vector<int>>& word,string& s,string& t){
    if(j==m-1)return;
    if(t[j]!=s[i])return;
    if(i&&s[i-1]==t[j+1]){
        if(dp[i-1][j+1]>dp[i][j]+1){
                dp[i-1][j+1]=dp[i][j]+1;
                DP(n,m,i-1,j+1,dp,word,s,t);
            }
    }
    if(i<n-1&&s[i+1]==t[j+1]){
        if(dp[i+1][j+1]>dp[i][j]+1){
                dp[i+1][j+1]=dp[i][j]+1;
                DP(n,m,i+1,j+1,dp,word,s,t);
            }
    }
    for(int x:word[s[i]-'a']){
        if(x==i)continue;
        if(x&&s[x-1]==t[j+1]){
            if(dp[x-1][j+1]>dp[i][j]+max(x-i,i-x)+1){
                dp[x-1][j+1]=dp[i][j]+max(x-i,i-x)+1;
                DP(n,m,x-1,j+1,dp,word,s,t);
            }
        }
        if(x<n-1&&s[x+1]==t[j+1]){
            if(dp[x+1][j+1]>dp[i][j]+max(x-i,i-x)+1){
                dp[x+1][j+1]=dp[i][j]+max(x-i,i-x)+1;
                DP(n,m,x+1,j+1,dp,word,s,t);
            }
        }
    }
}
int main(){
    int n,m;
    string s,t;
    cin>>n>>m>>s>>t;
    vector<vector<int>> dp(n,vector<int>(m+1,1e9)),word(26,vector<int>());
    for(int i=0;i<s.size();i++)word[s[i]-'a'].push_back(i);
    for(int x:word[t[0]-'a']){
        dp[x][0]=0;
        DP(n,m,x,0,dp,word,s,t);
    }
    int ans=1e9;
    for(int i=0;i<n;i++)ans=min(ans,dp[i][m-1]);
    if(ans==1e9)cout<<-1;
    else cout<<ans;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<s.size();i++)word[s[i]-'a'].push_back(i);
      |                 ~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 1 ms 296 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 656 KB Output is correct
2 Correct 241 ms 692 KB Output is correct
3 Correct 93 ms 684 KB Output is correct
4 Correct 146 ms 688 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Execution timed out 1079 ms 596 KB Time limit exceeded
8 Halted 0 ms 0 KB -