Submission #256493

#	Time	Username	Problem	Language	Result	Execution time	Memory
256493		shayan_p	Vim (BOI13_vim)	C++14	100 / 100	631 ms	9336 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)

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

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

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

int nxt[maxn][10], nxt2[maxn][10], lst[10], a[maxn];
int dp[maxn][10], DP[maxn], DP2[maxn], DP3[maxn];
vector<int> poses;

int dis(int a, int b){
    if(a > b)
	return inf;
    if(a == b)
	return 0;
    int mx = a;
    for(int i = 0; i < 9; i++){
	if(nxt[a][i] <= b)
	    mx = max(mx, nxt[a][i]);
    }
    return 2 + dis(mx, b);
}

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;
    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--){
	for(int j = 0; j < 9; j++)
	    nxt[i][j] = (lst[j] == -1 ? i : lst[j]);
	int id = (s[i] - 'a') - (s[i] > 'e');
	a[i] = id;
	lst[id] = i;
	for(int j = 0; j < 9; j++)
	    nxt2[i][j] = (lst[j] == -1 ? i : lst[j]);
    }

    for(int i = 0; i < maxn; i++){
	for(int j = 0; j < 10; j++)
	    dp[i][j] = inf;
	DP[i] = DP2[i] = DP3[i] = inf;
    }
    for(int i = poses.back(); i < maxn; i++){
	DP[i] = DP2[i] = DP3[i] = 0;
    }
    
    int pt = sz(poses) - 1;
    for(int i = poses.back() - 1; i >= 0; i--){
	for(int j = 0; j < 9; j++){
	    if(nxt[i][j] > i){
		DP3[i] = min(DP3[i], 2 + DP3[ nxt[i][j] ] + nxt[i][j] - i);		
	    }
	}
	for(int j = 0; j < 9; j++){
	    if(nxt[i][j] > i){
		if(nxt[i][j] < poses[pt]) // <= ? 
		    DP2[i] = min(DP2[i], 2 + DP2[ nxt[i][j] ]);
		else
		    DP2[i] = min(DP2[i], 2 + DP3[ nxt[i][j] ] + nxt[i][j] - poses[pt]);		
	    }
	}
	DP[i] = DP2[i];
	for(int j = 0; j < 9; j++){
	    int x = nxt[i][j];
	    if(x == i)
		continue;
	    if(x <= poses[pt]){
		DP[i] = min(DP[i], 2 + DP[x]);
	    }
	    else{
		for(int k = 0; k < 9; k++){
		    DP[i] = min(DP[i], 2 + x - poses[pt] + dis(poses[pt], nxt2[x][k]) + dp[x][k]);
		}
	    }
	}
	for(int j = 0; j < 9; j++){
	    int x = nxt2[i][j];
	    if(x <= poses[pt]){
		dp[i][j] = DP[x];
	    }
	    else{
		dp[i][j] = x - poses[pt] + DP3[x];
		for(int k = 0; k < 9; k++)
		    dp[i][j] = min(dp[i][j], x - poses[pt] + dis(poses[pt], nxt2[x][k]) + dp[x][k]);
	    }
	    for(int k = 0; k < 9; k++){
		int xx = nxt[i][k];
		if(xx == i)
		    continue;
		for(int k2 = 0; k2 < 9; k2++)
		    dp[i][j] = min(dp[i][j], 2 + xx - i + dis(x, nxt2[xx][k2]) + dp[xx][k2]);
	    }
	}
	if(pt > 0 && poses[pt-1] == i){
	    pt--;
	}
    }
    ans+= DP[0];
    return cout << ans << "\n", 0;
}

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