Submission #122195

#	Time	Username	Problem	Language	Result	Execution time	Memory
122195		Adhyyan1252	Vim (BOI13_vim)	C++11	27.78 / 100	49 ms	15488 KiB

vim

#include<bits/stdc++.h>

using namespace std;
#define INF 1e7
int main(){
	int n; cin>>n;
	vector<int> a(n+2);
	for(int i = 1; i <= n; i++){
		char c; cin>>c;
		a[i] = c - 'a';
	}
	
	vector<vector<int> > next(n+2, vector<int>(10, INF));
	for(int i = n; i > 0; i--){
		next[i] = next[i+1];
		next[i][a[i]] = i;
	}
	
	vector<vector<int> > pref(n+2, vector<int>(10, 0));
	for(int i = 1; i <= n; i++){
		pref[i] = pref[i-1];
		pref[i][a[i]]++;
	}
	
	vector<vector<int> > dp(n+2, vector<int>(10, INF));
	for(int i = 0; i < 10; i++){
		dp[n+1][i] = 0;
	}
	for(int i = n; i > 0; i--){
		for(int j = 0; j < 10; j++){
			
		int cur = next[i][j]; //cursor is here. need to delete all from i to n
		if(cur == INF) continue;
		//first come back to the leftest e
		if(j == 4){
			continue;
		}
		int indx = next[i][4];

		if(indx == INF){ //no e's after i
			dp[i][j] = 0;
		}else if(indx > cur){
			//this section has no e's so just move forward by exactly one fk
			for(int k = 0; k < 10; k++){
				if(k == 4) continue;
				dp[i][j] = min(dp[i][j], 2 + dp[cur+1][k]); //cursor moves to next[cur+1][k]
			}
		}else if(next[cur+1][4] == INF){
			int cost = cur - indx + pref[cur][4] - pref[indx-1][4];
			dp[i][j] = cost;
		}else{
			
			//first go left to reach leftest e. 
			int cost = cur - indx + pref[cur][4] - pref[indx-1][4];
			//jump from indx+1 to next[cur+1][k]
			
			//find next element, after
			int after = cur;
			for(int k = 0; k < 10; k++){
				if(k == 4) continue;
				after = min(after, next[indx][k]);
			}
			assert(after > indx);
			int oc = INF;
			for(int k = 0; k < 10; k++){
				if(k == 4) continue;
				if(next[cur+1][k] == INF) continue;
				oc = min(oc, dp[cur+1][k] + 2*(pref[next[cur+1][k]][k] - pref[after][k]));
			}
			dp[i][j] = min((int)INF, oc + cost);
		}	
	}
//		cout<<"DP "<<i<<" : ";
//		for(int j = 0; j < 10; j++){
//			cout<<dp[i][j]<<"\t";
//		}
//		cout<<endl;
	}
	int ans = dp[1][a[1]];
//	for(int i = 0; i < 10; i++){
//		ans = min(ans, dp[1][i]);
//	}
	cout<<ans<<endl;
}

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