oj.uz

답안 #256291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256291 2020-08-02T13:50:17 Z amoo_safar Vim (BOI13_vim) C++17
60 / 100
 456 ms 200988 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e3 + 10;
const int Inf = 1e9;
const ll Log = 30;

str s;
int dp[N][N];
int nx[N][12], nxe[N], ps[N], ps2[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n >> s;


	memset(nx, -1, sizeof nx);
	nxe[n - 1] = n - 1;
	for(int i = n - 2; i >= 0; i--){
		for(int j = 0; j < 10; j++) nx[i][j] = nx[i + 1][j];
		nx[i][s[i + 1] - 'a'] = i + 1;
		nxe[i] = (s[i] == 'e' ? nxe[i + 1] : i);
	}

	vector<int> E;
	ps2[0] = 1;
	for(int i = 1; i < n; i++){
		if(s[i] == 'e') E.pb(i);
		ps[i] = ps[i - 1] + (s[i] == 'e' ? 1 : 0);
		ps2[i] = ps2[i - 1] + (s[i] == 'e' ? 0 : 1);
	}

	int ce = E.size();

	memset(dp, 31, sizeof dp);
	dp[0][0] = 0;
	for(int j = 0; j < ce; j++){
		
		for(int i = 0; i < n; i++){
			if(s[i] == 'e') continue;

			for(int c = 0; c < 10; c++){
				if(nx[i][c] != -1) dp[nx[i][c]][j] = min(dp[nx[i][c]][j], dp[i][j] + 2);
			}
			if(E[j] < i){
				dp[ nxe[E[j]] ][ps[i]] = min(dp[ nxe[E[j]] ][ps[i]], dp[i][j] + ps2[i] - ps2[nxe[E[j]]]);
			}
		}
	}
	int ans = Inf;
	for(int i = 0; i < n; i++){
		ans = min(ans, dp[i][ce] + ce + ce);
	}
	//debug(dp[3][2]);
	//debug(nx[3][5]);
	//debug(dp[9][2]);

	cout << ans << '\n';
	return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 98808 KB Output is correct
2 Correct 53 ms 98812 KB Output is correct
3 Correct 54 ms 98808 KB Output is correct
4 Correct 52 ms 98808 KB Output is correct
5 Correct 53 ms 98808 KB Output is correct
6 Correct 54 ms 98884 KB Output is correct
7 Correct 55 ms 98808 KB Output is correct
8 Correct 56 ms 98808 KB Output is correct
9 Correct 53 ms 98936 KB Output is correct
10 Correct 50 ms 98808 KB Output is correct
11 Correct 57 ms 98808 KB Output is correct
12 Correct 50 ms 98808 KB Output is correct
13 Correct 60 ms 98864 KB Output is correct
14 Correct 55 ms 98832 KB Output is correct
15 Correct 52 ms 98808 KB Output is correct
16 Correct 53 ms 98808 KB Output is correct
17 Correct 61 ms 98808 KB Output is correct
18 Correct 61 ms 98808 KB Output is correct
19 Correct 60 ms 98808 KB Output is correct
20 Correct 59 ms 98936 KB Output is correct
21 Correct 53 ms 98808 KB Output is correct
22 Correct 54 ms 98808 KB Output is correct
23 Correct 60 ms 98808 KB Output is correct
24 Correct 53 ms 98808 KB Output is correct
25 Correct 60 ms 98808 KB Output is correct
26 Correct 63 ms 98808 KB Output is correct
27 Correct 62 ms 98808 KB Output is correct
28 Correct 58 ms 98796 KB Output is correct
29 Correct 54 ms 98796 KB Output is correct
30 Correct 59 ms 98808 KB Output is correct
31 Correct 60 ms 98812 KB Output is correct
32 Correct 59 ms 98808 KB Output is correct
33 Correct 60 ms 98808 KB Output is correct
34 Correct 60 ms 98808 KB Output is correct
35 Correct 53 ms 98808 KB Output is correct
36 Correct 57 ms 98880 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 99064 KB Output is correct
2 Correct 435 ms 99032 KB Output is correct
3 Correct 177 ms 98808 KB Output is correct
4 Correct 440 ms 98948 KB Output is correct
5 Correct 421 ms 99068 KB Output is correct
6 Correct 345 ms 98808 KB Output is correct
7 Correct 436 ms 99064 KB Output is correct
8 Correct 456 ms 99064 KB Output is correct
9 Correct 425 ms 98952 KB Output is correct
10 Correct 393 ms 99044 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 163 ms 200448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 167 ms 200696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 177 ms 200968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 153 ms 200828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 161 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 167 ms 200948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 153 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 160 ms 200868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 162 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 168 ms 200888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 183 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 188 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 183 ms 200884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 173 ms 200988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 211 ms 200824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 200 ms 200576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 211 ms 200568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 205 ms 200568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 194 ms 200720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 186 ms 200792 KB Execution killed with signal 11 (could be triggered by violating memory limits)