oj.uz

답안 #485560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485560 2021-11-08T09:18:33 Z groupATSU Bajka (COCI20_bajka) C++14
70 / 70
 31 ms 1296 KB 
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#define aldgebu return
#define ff first
#define sc second
#define pb push_back
#define pii pair <int,int>
#define p push
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const ll inf = 1e9;
const ll mod = 1e9 + 7;


void Dontfuckedup(){
	int dp[501][501];
	for (int i = 0; i <= 500; i++)
		for (int j = 0; j <= 500; j++)
			dp[i][j] = inf;

	int M, N;
	string s1, s;
	cin >> M >> N >> s1 >> s;

	vector <int> pos[26];
	for (int i = 0; i < M; i++)
		pos[s1[i] - 'a'].pb(i);

	int cur = s[0] - 'a';
	for (int i = 0; i < pos[cur].size(); i++){
		dp[pos[cur][i]][0] = 0;
	}

	int val, lst;
	vector <int> v;
	for (int i = 1; i < N; i++){
		cur = s[i] - 'a';
		lst = s[i - 1] - 'a';
		v.clear();
		for (int j = 0; j < pos[cur].size(); j++){
			val = pos[cur][j];
			if (val - 1 >= 0 && s1[val - 1] == s[i - 1])
				v.pb(val - 1);
			if (val + 1 < M && s1[val + 1] == s[i - 1])
				v.pb(val + 1);
		}

		for (int j = 0; j < v.size(); j++){
			for (int k = 0; k < pos[lst].size(); k++){
				dp[v[j]][i - 1] = min(dp[v[j]][i - 1], dp[pos[lst][k]][i - 1] + abs(pos[lst][k] - v[j]));
			}
		}

		for (int j = 0; j < pos[cur].size(); j++){
			val = pos[cur][j];
			if (val - 1 >= 0 && s1[val - 1] == s[i - 1])
				dp[pos[cur][j]][i] = min(dp[pos[cur][j]][i], dp[val - 1][i - 1] + 1);
			if (val + 1 < M && s1[val + 1] == s[i - 1])
				dp[pos[cur][j]][i] = min(dp[pos[cur][j]][i], dp[val + 1][i - 1] + 1);
		}
	}

	int ans = inf;
	cur = s[N - 1] - 'a';
	for (int i = 0; i < pos[cur].size(); i++){
		ans = min(ans, dp[pos[cur][i]][N - 1]);
	}

	cout << (ans == inf ? -1 : ans);
}

int32_t main () {

	ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1; //cin >> T;
    while (T--)Dontfuckedup();

    return 0;
}

Compilation message

bajka.cpp: In function 'void Dontfuckedup()':
bajka.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < pos[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
bajka.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j = 0; j < pos[cur].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~
bajka.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int j = 0; j < v.size(); j++){
      |                   ~~^~~~~~~~~~
bajka.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for (int k = 0; k < pos[lst].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~~
bajka.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int j = 0; j < pos[cur].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~
bajka.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < pos[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1292 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1288 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1292 KB Output is correct
7 Correct 3 ms 1296 KB Output is correct
8 Correct 15 ms 1228 KB Output is correct
9 Correct 31 ms 1228 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 3 ms 1228 KB Output is correct