oj.uz

Submission #398937

# Submission time Handle Problem Language Result Execution time Memory
398937 2021-05-04T22:32:00 Z retsiger Bajka (COCI20_bajka) C++14
70 / 70
 91 ms 2268 KB 
#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.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 4 ms 708 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 21 ms 972 KB Output is correct
8 Correct 91 ms 2268 KB Output is correct
9 Correct 48 ms 1484 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 14 ms 848 KB Output is correct