Submission #137488

#	Time	Username	Problem	Language	Result	Execution time	Memory
137488		gs14004	Vim (BOI13_vim)	C++17	100 / 100	175 ms	34920 KiB

vim

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 70005;

int n;
char str[MAXN], buf[MAXN];
int chk[MAXN];
int dp[MAXN][10];
int d2[MAXN][10][10];

int f(int v, int w);
int g(int v, int win, int wout);

int g(int v, int win, int wout){
	if(v == n - 1) return 1e9;
	if(~d2[v][win][wout]) return d2[v][win][wout];
	int ret = 1e9;
	if(win + 'a' == str[v + 1] && wout + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, f(v + 1, i) + 3);
		}
		for(int i=0; i<10; i++){
			for(int j=0; j<10; j++){
				ret = min(ret, g(v + 1, i, j) + 5);
			}
		}
	}
	else if(win + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, g(v + 1, i, wout) + 3);
		}
		ret = min(ret, f(v + 1, wout) + 1);
	}
	else if(wout + 'a' == str[v + 1]){
		for(int i=0; i<10; i++){
			ret = min(ret, g(v + 1, win, i) + 3);
		}
	}
	else{
		ret = min(ret, g(v + 1, win, wout) + 1);
	}
	return d2[v][win][wout] = ret;
}

int f(int v, int w){
	if(v == n - 1) return w == 4 ? 0 : 1e9;
	if(~dp[v][w]) return dp[v][w];
	int ret = 1e9;
	if(str[v + 1] == w + 'a'){
		for(int i=0; i<10; i++){
			ret = min(ret, f(v + 1, i) + 2);
		}
		return dp[v][w] = ret;
	}
	for(int i=0; i<10; i++){
		ret = min(ret, g(v + 1, w, i) + 2);
	}
	if(!chk[v + 1]) ret = min(ret, f(v + 1, w));
	return dp[v][w] = ret;
}

int main(){
	scanf("%d %s",&n,buf);
	n = 0;
	int ecnt = 0;
	for(int i=0; buf[i]; i++){
		if(buf[i] == 'e'){
			ecnt++;
			chk[n] = 1;
		}
		else str[n++] = buf[i];
	}
	memset(dp, -1, sizeof(dp));
	memset(d2, -1, sizeof(d2));
	int ret = 1e9;
	for(int i=0; i<10; i++){
		ret = min(ret, f(0, i));
	}
	cout << ret + ecnt * 2 << endl;
}

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s",&n,buf);
  ~~~~~^~~~~~~~~~~~~~~~

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