oj.uz

Submission #955527

# Submission time Handle Problem Language Result Execution time Memory
955527 2024-03-30T19:46:13 Z shezitt Bajka (COCI20_bajka) C++14
70 / 70
 42 ms 1312 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define ii pair<int,int>
#define F first
#define S second
#define endl '\n'

const int N = 305;
int dp[N][N];

signed main(){
    int n, m;
    cin >> n >> m;
    string fear, fav;
    cin >> fear >> fav;

    for(int i=0; i<=m; ++i){
        for(int j=0; j<=n; ++j){
            dp[i][j] = 4e18;
        }
    }

    for(int j=0; j<n; ++j){
        if(fear[j] == fav[0]){
            dp[1][j] = 0;
        }
    }

    for(int i=1; i<m; ++i){
        for(int j=0; j<n; ++j){
            for(int k=0; k<n; ++k){
                if(fear[k] == fear[j]){
                    dp[i][k] = min(dp[i][k], dp[i][j] + abs(j - k));
                }
            }
        }
        for(int j=0; j<n; ++j){
            // left
            if(j > 0 && fear[j-1] == fav[i]){
                dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j] + 1);
            }
            // right
            if(j+1 < n && fear[j+1] == fav[i]){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1);
            }
        }
    }

    int ans = 4e18;
    for(int j=0; j<n; ++j){
        ans = min(ans, dp[m][j]);
    }
    cout << (ans == 4e18 ? -1 : ans);

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 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 38 ms 1300 KB Output is correct
2 Correct 42 ms 1116 KB Output is correct
3 Correct 34 ms 1116 KB Output is correct
4 Correct 36 ms 1116 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 36 ms 1312 KB Output is correct
8 Correct 39 ms 1116 KB Output is correct
9 Correct 42 ms 1136 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 36 ms 956 KB Output is correct