oj.uz

Submission #661047

# Submission time Handle Problem Language Result Execution time Memory
661047 2022-11-24T06:07:55 Z Kenpar Bajka (COCI20_bajka) C++17
20 / 70
 1 ms 212 KB 
#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define endl '\n'

const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll MAX = 2 * 1e5;
char getLast(string s){
	return s[s.size()-1];
}
void solve(){
	int n,m;
	cin>>n>>m;

	string a,b; cin>>a>>b;
	vector<ll> dp(n, INF);

	for(int i = 0; i < n; i++){
		if(a[i] == getLast(b)){
			dp[i] = 0;
		}
	}

	while(b.size() > 1){
		char top = getLast(b);
		b.pop_back();

		#ifdef DEBUG
		for(int z : dp){
			cout<<z<<" ";
		}

		#endif


		char cur = getLast(b);
		vector<ll> temp(n, INF); 

		bool check = false;

		for(ll i = 0; i < n; i++){

			if(a[i] != top) continue;
			
			if(i - 1 >= 0 && a[i-1] == cur){
				check = true;

				temp[i-1] = min(dp[i] + 1, temp[i-1]);

				for(ll j = i-2; j >= 0; j--){
					if(a[j] == cur){
						temp[j] = min((i-1) - j  + temp[i - 1], temp[j]);
					}
				}
			}
			
			if(i + 1 < n && a[i+1] == cur){
				check = true;
				temp[i+1] = min(dp[i] + 1, temp[i+1]);

				for(ll j = i+2; j < n; j++){
					if(a[j] == cur){
						temp[j] = min(j - (i + 1) + temp[i + 1], temp[j]);
					}
				}
			}

			
		}

		dp = temp;

		if(!check){
			cout<<-1;
			return;
		}

	}	
	#ifdef DEBUG
	for(int z : dp){
		cout<<z<<" ";
	}

	#endif
	ll ans = INF;

	for(ll z : dp){
		ans = min(z, ans);
	}

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


int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(NULL);
    int t = 1;

    //cin>>t;
    int temp = t;
    while(t--){
        //cout<<"Case #"<<temp - t<<" > "<<endl;
        solve();

        cout<<endl;
    }

    cout.flush();
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:105:9: warning: unused variable 'temp' [-Wunused-variable]
  105 |     int temp = t;
      |         ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -