Submission #256393

# Submission time Handle Problem Language Result Execution time Memory
256393 2020-08-02T16:06:18 Z Saboon Vim (BOI13_vim) C++14
50 / 100
6 ms 1408 KB
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;

const int maxn = 500 + 10;

int nex[maxn][12];
int dp[maxn][maxn];
int pd[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	for (int i = 0; i < 10; i++){
		int last = -1;
		for (int j = n-1; j >= 0; j--){
			if (last == -1)
				nex[j][i] = j;
			else
				nex[j][i] = last;
			if ((int)(s[j] - 'a') == i and s[j] != 'e')
				last = j;
		}
	}
	vector<int> e;
	for (int i = 0; i < n; i++)
		if (s[i] == 'e')
			e.push_back(i);
	if (e.empty())
		return cout << 0 << endl, 0;
	int m = e.size();
	memset(dp, 63, sizeof dp);
	dp[0][0] = 0;
	for (int i = 0; i < m; i++){
		memset(pd, 63, sizeof pd);
		for (int j = 0; j <= i; j++){
			if (j > 0)
				pd[e[j-1]+1] = dp[i][j];
			else
				pd[0] = dp[i][j];
		}
		for (int j = 0; j < n; j++)
			for (int c = 0; c < 10; c++)
				if (nex[j][c] != j)
					pd[nex[j][c]] = min(pd[nex[j][c]], pd[j] + 2);
		int it = 0;
		for (int idx = 0; idx < n; idx ++){
			if (s[idx] == 'e')
				continue;
			while (it < m and e[it] < idx)
				it ++;
			if (it <= i)
				continue;
			dp[it][i+1] = min(dp[it][i+1], pd[idx] + (idx-e[i]) + (it-i));
		}
	}
	int answer = 4*n;
	for (int i = 1; i <= m; i++)
		answer = min(answer, dp[m][i]);
	cout << answer << endl;
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 4 ms 1408 KB Output is correct
8 Correct 1 ms 1408 KB Output is correct
9 Correct 1 ms 1408 KB Output is correct
10 Correct 1 ms 1408 KB Output is correct
11 Correct 1 ms 1408 KB Output is correct
12 Correct 1 ms 1408 KB Output is correct
13 Correct 5 ms 1408 KB Output is correct
14 Correct 4 ms 1408 KB Output is correct
15 Correct 3 ms 1408 KB Output is correct
16 Correct 3 ms 1408 KB Output is correct
17 Correct 4 ms 1408 KB Output is correct
18 Correct 3 ms 1408 KB Output is correct
19 Correct 2 ms 1408 KB Output is correct
20 Correct 4 ms 1408 KB Output is correct
21 Correct 3 ms 1408 KB Output is correct
22 Correct 4 ms 1408 KB Output is correct
23 Correct 2 ms 1408 KB Output is correct
24 Correct 2 ms 1408 KB Output is correct
25 Correct 3 ms 1408 KB Output is correct
26 Correct 3 ms 1408 KB Output is correct
27 Correct 4 ms 1408 KB Output is correct
28 Correct 5 ms 1408 KB Output is correct
29 Correct 4 ms 1408 KB Output is correct
30 Correct 3 ms 1408 KB Output is correct
31 Correct 3 ms 1408 KB Output is correct
32 Correct 3 ms 1408 KB Output is correct
33 Correct 3 ms 1408 KB Output is correct
34 Correct 4 ms 1408 KB Output is correct
35 Correct 4 ms 1408 KB Output is correct
36 Correct 4 ms 1408 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 2 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 1 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 1 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 2 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 2 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 1 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)