Submission #106143

#	Time	Username	Problem	Language	Result	Execution time	Memory
106143		ihdignite	Vim (BOI13_vim)	C++14	50 / 100	2073 ms	203136 KiB

vim

#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxN=5e3;
int n, ans, d[mxN][mxN], nxt[mxN+1][10];
string s;
priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> pq;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	fill(nxt[n], nxt[n]+10, n);
	for(int i=n-1; ~i; --i) {
		memcpy(nxt[i], nxt[i+1], 40);
		nxt[i][s[i]-'a']=i;
	}
	int e=n-1;
	while(e&&s[e-1]^'e')
		--e;
	memset(d, 0x3f, sizeof(d));
	d[0][0]=0;
	pq.push({0, 0, 0});
	while(pq.size()) {
		ar<int, 3> u=pq.top();
		pq.pop();
		if(u[0]>d[u[1]][u[2]])
			continue;
		if(u[1]>=e) {
			ans=u[0];
			break;
		}
		vector<ar<int, 3>> t;
		for(int k=0; k<10; ++k)
			if(k^4&&nxt[u[2]+1][k]<n)
				t.push_back({2, u[1], nxt[u[2]+1][k]});
		if(u[2])
			t.push_back({1, u[1], u[2]-1});
		if(nxt[u[1]+1][4]<u[2]) {
			int y=n;
			for(int j=0; j<10; ++j)
				if(j^4)
					y=min(y, nxt[nxt[u[1]+1][4]][j]);
			t.push_back({u[2]-nxt[u[1]+1][4], u[2], y});
		}
		for(ar<int, 3> v : t) {
			if(u[0]+v[0]<d[v[1]][v[2]]) {
				d[v[1]][v[2]]=u[0]+v[0];
				pq.push({u[0]+v[0], v[1], v[2]});
			}
		}
	}
	for(char c : s)
		ans+=c=='e';
	cout << ans;
}

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