oj.uz

Submission #379970

# Submission time Handle Problem Language Result Execution time Memory
379970 2021-03-19T20:57:59 Z PedroBigMan Bajka (COCI20_bajka) C++14
70 / 70
 27 ms 512 KB 
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N,M; cin>>N>>M; string s,f; cin>>s; cin>>f;
	vector<pair<char,char> > adj; REP(i,0,N-1) {adj.pb(mp(s[i],s[i+1])); adj.pb(mp(s[i+1],s[i]));}
	sort(whole(adj)); pair<char,char> tofind; vector<pair<char,char> >::iterator it;
	REP(i,0,M-1)
	{
		tofind=mp(f[i],f[i+1]);
		it=lower_bound(whole(adj),tofind);
		if(it==adj.end() || *it!=tofind) {cout<<-1<<endl; return 0;}
	}
	vector<pl> dp; //pairs (position of letter,distance until now)
	vector<pl>::iterator it2;
	REP(i,0,N) {if(s[i]==f[0]) {dp.pb(mp(i,0LL));}}
	REP(i,1,M)
	{
		vector<pl> newdp;
		REP(j,0,N)
		{
			if(s[j]==f[i]) {newdp.pb(mp(j,INF));}
		}
		REP(j,0,newdp.size())
		{
			ll pos=newdp[j].ff;
			if(pos!=0 && s[pos-1]==f[i-1])
			{
				it2=lower_bound(whole(dp),mp(pos-1LL,0LL));
				newdp[j].ss=min(newdp[j].ss,it2->ss +1LL);
			}
			if(pos!=N-1 && s[pos+1]==f[i-1])
			{
				it2=lower_bound(whole(dp),mp(pos+1,0LL));
				newdp[j].ss=min(newdp[j].ss,it2->ss +1LL);
			}
		}
		REP(j,0,newdp.size())
		{
			REP(z,0,newdp.size())
			{
				if(j==z) {continue;}
				newdp[z].ss=min(newdp[z].ss,newdp[j].ss+abs(newdp[j].ff-newdp[z].ff));
			}
		}
		dp=newdp; 
	}
	ll ans=INF;
	REP(i,0,dp.size()) {ans=min(ans,dp[i].ss);}
	cout<<ans<<endl;
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 15 ms 364 KB Output is correct
9 Correct 27 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 364 KB Output is correct