oj.uz

Submission #318335

# Submission time Handle Problem Language Result Execution time Memory
318335 2020-11-01T09:44:55 Z nkft Bajka (COCI20_bajka) C++17
70 / 70
 51 ms 1140 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define nbits(x) __builtin_popcount(x)
#define gcd(x, y) __gcd(x, y)
#define SYNC_OFF ios::sync_with_stdio(0); cin.tie(0);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;  
const int MOD = 1e9 + 7; // 998244353;
const int N = 301;
const int INF = 1e15; // 1e18;
const double PI = acos(-1);
const int dx[] = {-1,0,1,0,-1,1,1,-1};
const int dy[] = {0,1,0,-1,1,1,-1,-1};
int powmod(int a, int b, int m = MOD) {
    int res = 1;
    a %= m; assert(b >= 0);
    for (; b; b>>=1) {
        if (b & 1) res = res*a % m;
        a = a*a % m;
    }
    return res;
}

int n, m;
string s, f;
int dp[N][N];

// dp[i][j] =  at i-th pos in s & need to make f[j]
int solve(int i, int j) {
    if (j == m) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int ans = INF;
    for (int k = 0; k < n; k++) {
        if (s[i] == s[k]) {
            if (k+1 < n && s[k+1] == f[j]) {
                ans = min(ans, solve(k+1, j+1) + abs(i-k) + 1);
            }
            if (0 <= k-1 && s[k-1] == f[j]) {
                ans = min(ans, solve(k-1, j+1) + abs(i-k) + 1);
            }
        }
    }
    return dp[i][j] = ans;
}

signed main() {
    SYNC_OFF;
    cin >> n >> m >> s >> f;
    memset(dp, -1, sizeof dp);
    int ans = INF;
    for (int i = 0; i < n; i++) {
        if (s[i] == f[0]) {
            ans = min(ans, solve(i, 1));
        }
    }
    cout << (ans == INF ? -1 : ans) << "\n"; 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1140 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 2 ms 1060 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 9 ms 1004 KB Output is correct
8 Correct 51 ms 1004 KB Output is correct
9 Correct 48 ms 1120 KB Output is correct
10 Correct 1 ms 1004 KB Output is correct
11 Correct 6 ms 1004 KB Output is correct