Submission #256278

#	Time	Username	Problem	Language	Result	Execution time	Memory
256278		shayan_p	Vim (BOI13_vim)	C++14	60 / 100	240 ms	34384 KiB

vim

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 5010, mod = 1e9 + 7, inf = 1e9 + 10;

int dp[maxn][maxn];
int nxt[maxn][10], lst[10];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    string _s, s;
    cin >> _s;
    int ans = 0;
    vector<int> poses;
    for(int i = 0; i < n; i++){
	if(_s[i] == 'e')
	    ans+= 2;
	if(_s[i] == 'e' && _s[i + 1] != 'e')
	    poses.PB(sz(s));
	if(_s[i] != 'e')
	    s+= _s[i];	
    }
    memset(lst, -1, sizeof lst);
    memset(nxt, -1, sizeof nxt);
    n = sz(s);
    for(int i = n-1; i >= 0; i--){
	memcpy(nxt[i], lst, sizeof lst);
	int id = (s[i] - 'a') - (s[i] > 'e');
	lst[id] = i;
    }
    for(int i = sz(poses)-1; i >= 0; i--){
	int pt = sz(poses)-1;
	for(int j = n-1; j >= 0; j--){
	    dp[i][j] = inf;
	    if(pt >= i)
		dp[i][j] = j - poses[i] + dp[pt + 1][poses[i]];
	    for(int k = 0; k < 9; k++)
		if(nxt[j][k] != -1)
		    dp[i][j] = min(dp[i][j], 2 + dp[i][nxt[j][k]]);	    
	    if(poses[pt] == j)
		pt--;
	}
    }
    ans+= dp[0][0];
    return cout << ans << "\n", 0;
}

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