Submission #398937

#	Time	Username	Problem	Language	Result	Execution time	Memory
398937		retsiger	Bajka (COCI20_bajka)	C++14	70 / 70	91 ms	2268 KiB

bajka

#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

typedef pair <int, int> ii;
typedef pair <int, ii> iii;

const int maxn = 305, INF = 1e9;

int N, M;
int dp[maxn][maxn];
vector <int> loc[26];
string S, T;

bool cmin(int &a, int b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
//  freopen("cc.out", "w", stdout);
  cin >> N >> M >> S >> T;
  for (int i = 0; i < N; ++i) {
    loc[S[i] - 'a'].push_back(i);
  }
  memset(dp, 0x3f, sizeof dp);
  priority_queue<iii, vector<iii>, greater<iii>> q;
  for (int i = 0; i < N; ++i) {
    if (S[i] == T[0]) {
      dp[0][i] = 0;
      q.push({0, ii(0, i)});
    }
  }
  int ans = INF;
  while (!q.empty()) {
    iii cur = q.top(); q.pop();
    int u = cur.x, i = cur.y.x, j = cur.y.y;
    if (u != dp[i][j]) continue;
    if (i == M - 1) {
      ans = min(ans, dp[i][j]);
      continue;
    }
    if (j && S[j - 1] == T[i + 1]) {
      if (cmin(dp[i + 1][j - 1], dp[i][j] + 1)) {
        q.push({dp[i + 1][j - 1], ii(i + 1, j - 1)});
      }
    }
    if (j + 1 < N && S[j + 1] == T[i + 1]) {
      if (cmin(dp[i + 1][j + 1], dp[i][j] + 1)) {
        q.push({dp[i + 1][j + 1], ii(i + 1, j + 1)});
      }
    }
    int c = S[j] - 'a';
    for (int x : loc[c]) {
      if (cmin(dp[i][x], dp[i][j] + abs(j - x))) {
        q.push({dp[i][x], ii(i, x)});
      }
    }
  }
  if (ans == INF) ans = -1;
  cout << ans << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50