Submission #491275

#	Time	Username	Problem	Language	Result	Execution time	Memory
491275		AdamGS	Vim (BOI13_vim)	C++14	30.56 / 100	416 ms	177452 KiB

vim

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define st first
#define nd second
const int LIM=7e4+7, INF=1e9+7;
vector<pair<int,int>>S[LIM];
vector<pair<pair<int,int>,int>>V[LIM][10];
int kiedy[10], nxt[LIM][10], ostatni[LIM], odl[LIM][10];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, lst=-1;
	string s;
	cin >> n >> s;
	rep(i, n) {
		if(s[i]=='e') {
			s[i]='a';
			lst=i;
		} else if(s[i]=='a') s[i]='e';
	}
	rep(i, 10) kiedy[i]=INF;
	for(int i=n-1; i>=0; --i) {
		rep(j, 10) nxt[i][j]=kiedy[j];
		for(int j=1; j<10; ++j) if(kiedy[j]<INF) {
			S[kiedy[j]].pb({j, 2});
		}
		if(i<n-1) S[i].pb({i+1, 1});
		kiedy[s[i]-'a']=i;
		ostatni[i]=INF;
	}
	priority_queue<pair<int,pair<int,int>>>q;
	q.push({0, {lst, 0}});
	while(!q.empty()) {
		int o=-q.top().st, p=q.top().nd.st; q.pop();
		if(ostatni[p]<=o) continue;
		ostatni[p]=o;
		for(auto i : S[p]) if(ostatni[i.st]>o+i.nd) {
			q.push({-o-i.nd, {i.st, 0}});
		}
	}
	rep(i, n) {
		for(int j=1; j<10; ++j) if(nxt[i][j]<INF) {
			if(nxt[i][0]>nxt[i][j]) {
				V[i][0].pb({{nxt[i][j], 0}, 2});
			} else {
				int c=j;
				if(nxt[i][0]+1==nxt[i][j]) c=0;
				V[i][0].pb({{nxt[i][0]+1, c}, 2+nxt[i][j]-nxt[i][0]});
			}
		}
		for(int j=1; j<10; ++j) if(nxt[i][j]<INF) {
			for(int l=1; l<10; ++l) if(nxt[i][l]<INF) {
				int p=nxt[i][j];
				if(nxt[p][0]>nxt[i][l]) {
					V[i][j].pb({{nxt[i][l], 0}, 2});
				} else {
					int c=l;
					if(nxt[p][0]+1==nxt[i][l]) c=0;
					V[i][j].pb({{nxt[p][0]+1, c}, 2+nxt[i][l]-nxt[p][0]});
				}
			}
		}
	}
	int ans=INF;
	rep(i, n) rep(j, 10) odl[i][j]=INF;
	q.push({0, {0, 0}});
	while(!q.empty()) {
		int o=-q.top().st, a=q.top().nd.st, b=q.top().nd.nd; q.pop();
		if(odl[a][b]<=o) continue;
		odl[a][b]=o;
		int p=nxt[a][b];
		if(!b) p=a;
		if(nxt[p][0]==INF) {
			ans=min(ans, o);
		} else {
			ans=min(ans, o+ostatni[a]+lst-nxt[p][0]);
		}
		for(auto i : V[a][b]) if(odl[i.st.st][i.st.nd]>o+i.nd) {
			q.push({-o-i.nd, {i.st.st, i.st.nd}});
		}
	}
	rep(i, n) if(s[i]=='a') ++ans;
	cout << ans << '\n';
}

• Subtask 1: 30.555555555555557 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40