Submission #106137

#	Time	Username	Problem	Language	Result	Execution time	Memory
106137		ihdignite	Vim (BOI13_vim)	C++14	42.50 / 100	52 ms	6136 KiB

vim

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

const int mxN=7e4;
int n, ans=1e9, dp[mxN][10], nxt[mxN+1][10];
string s;

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;
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][s[0]-'a']=0;
	int e=n-1;
	while(e&&s[e-1]^'e')
		--e;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<10; ++j) {
			if(j==4)
				continue;
			if(nxt[i][j]>=e)
				ans=min(dp[i][j], ans);
			int y=n;
			for(int k=0; k<10; ++k)
				if(k^4)
					y=min(nxt[nxt[nxt[i][j]][4]][k], y);
			for(int k=0; k<10; ++k) {
				int a=nxt[i+1][k], nf=1;
				if(a<=nxt[i][j]) {
					a=nxt[nxt[i][j]+1][k];
					++nf;
				}
				if(k==4||a>=n)
					continue;
				int x=min(a, y);
				dp[x][k]=min(dp[i][j]+2*nf+max(a-nxt[nxt[i][j]][4], 0), dp[x][k]);
			}
		}
	}
	for(char c : s)
		ans+=c=='e';
	cout << ans;
}

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