Submission #248789

#	Time	Username	Problem	Language	Result	Execution time	Memory
248789		mieszko11b	Vim (BOI13_vim)	C++14	55 / 100	663 ms	205560 KiB

vim

#include <bits/stdc++.h>

using namespace std;

int n;
char c[70007];
int pre[70007];
int nxt[10][70007];
int dp[5007][5007];	// ostatni usuniety, pozycja kursora

int main() {
	scanf("%d", &n);
	scanf(" %s", c + 1);
	
	int cnte = 0;
	for(int i = 1 ; i <= n ; i++) {
		if(c[i] == 'e')
			pre[i] = i, cnte++;
		else
			pre[i] = pre[i - 1];
	}
	
	for(int i = n - 1 ; i >= 0 ; i--) {
		for(char cc = 'a' ; cc <= 'j' ; cc++) {
			if(c[i + 1] == cc)
				nxt[cc - 'a'][i] = i + 1;
			else
				nxt[cc - 'a'][i] = nxt[cc - 'a'][i + 1];
		}
	}
	
	for(int i = 0 ; i < 5005 ; i++)
		for(int j = 0 ; j < 5005 ; j++)
			dp[i][j] = 1e9;
	
	dp[0][1] = cnte;
	for(int i = 0 ; i < n ; i++) {
		if(i == 0 || c[i] == 'e') {
			for(int j = 1 ; j <= n ; j++) {
				if(j < n) {
					for(int k = 0 ; k < 10 ; k++)
						if(k != 4 && nxt[k][j])
							dp[i][nxt[k][j]] = min(dp[i][nxt[k][j]], dp[i][j] + 2);
				}
				
				if(pre[j] > i)
					dp[pre[j]][nxt[4][i] + 1] = min(dp[pre[j]][nxt[4][i] + 1],
						dp[i][j] + j - nxt[4][i]);
			}
		}
	}
	
	int  res = 1e9;
	for(int j = 1 ; j <= n ; j++)
		res = min(res, dp[pre[n]][j]);
		
	printf("%d\n", res);
	
	return 0;
}

Compilation message (stderr)

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

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