oj.uz

답안 #256377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256377 2020-08-02T15:49:29 Z shayan_p Vim (BOI13_vim) C++14
75.6111 / 100
 2000 ms 286820 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 70010, mod = 1e9 + 7, inf = 1e9 + 10;

int nxt[maxn][10], lst[10];

unordered_map<int, int> dp[maxn];
vector<int> poses;

int solve(int i, int j){
    if(i >= sz(poses))
	return 0;
    if(dp[i].count(j))
	return dp[i][j];
    int ans = inf;
    if(j >= poses[i])
	ans =  j - poses[i] + solve( upper_bound(poses.begin(), poses.end(), j) - poses.begin(), poses[i] );
    if(nxt[ poses[i] ][8] + 10 < j)
	return dp[i][j] = ans;
    int pt = lower_bound(nxt[j], nxt[j] + 10, poses[i]) - nxt[j];
    for(int w = 8 ; w >= 0 && nxt[j][w] != j && w >= pt-1; w--)
	ans = min(ans, 2 + solve(i, nxt[j][w]));
    return dp[i][j] = ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    string _s, s;
    cin >> _s;
    int ans = 0;
    for(int i = 0; i < n; i++){
	if(_s[i] == 'e')
	    ans+= 2;
	if(_s[i] == 'e' && _s[i + 1] != 'e')
	    poses.PB(sz(s));
	if(_s[i] != 'e')
	    s+= _s[i];	
    }
    memset(lst, -1, sizeof lst);
    memset(nxt, -1, sizeof nxt);
    n = sz(s);
    for(int i = n-1; i >= 0; i--){
	for(int j = 0; j < 9; j++)
	    nxt[i][j] = (lst[j] == -1 ? i : lst[j]);
	sort(nxt[i], nxt[i] + 9);
	nxt[i][9] = inf;
	int id = (s[i] - 'a') - (s[i] > 'e');
	lst[id] = i;
    }
    ans+= solve(0, 0);
    return cout << ans << "\n", 0;
}

Subtask #1
48.6111111111 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8064 KB Output is correct
2 Correct 8 ms 7680 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 8 ms 7552 KB Output is correct
5 Correct 15 ms 8320 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 9 ms 7808 KB Output is correct
8 Correct 4 ms 6912 KB Output is correct
9 Correct 4 ms 6912 KB Output is correct
10 Correct 5 ms 6912 KB Output is correct
11 Correct 4 ms 6912 KB Output is correct
12 Correct 4 ms 6912 KB Output is correct
13 Correct 11 ms 7936 KB Output is correct
14 Correct 8 ms 7680 KB Output is correct
15 Correct 6 ms 7424 KB Output is correct
16 Correct 8 ms 7552 KB Output is correct
17 Correct 8 ms 7552 KB Output is correct
18 Correct 9 ms 7424 KB Output is correct
19 Incorrect 10 ms 7808 KB Output isn't correct
20 Correct 13 ms 7808 KB Output is correct
21 Correct 9 ms 7552 KB Output is correct
22 Correct 13 ms 8320 KB Output is correct
23 Correct 9 ms 7680 KB Output is correct
24 Correct 10 ms 7680 KB Output is correct
25 Correct 7 ms 7296 KB Output is correct
26 Correct 6 ms 7168 KB Output is correct
27 Correct 8 ms 7552 KB Output is correct
28 Correct 9 ms 7680 KB Output is correct
29 Correct 10 ms 7808 KB Output is correct
30 Correct 8 ms 7552 KB Output is correct
31 Correct 11 ms 7424 KB Output is correct
32 Correct 7 ms 7296 KB Output is correct
33 Correct 6 ms 7168 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 9 ms 7680 KB Output is correct
36 Correct 10 ms 7808 KB Output is correct

Subtask #2
9.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 13688 KB Output is correct
2 Correct 59 ms 15864 KB Output is correct
3 Correct 36 ms 11768 KB Output is correct
4 Correct 50 ms 13688 KB Output is correct
5 Correct 168 ms 28696 KB Output is correct
6 Correct 806 ms 92408 KB Output is correct
7 Correct 156 ms 28252 KB Output is correct
8 Correct 68 ms 15864 KB Output is correct
9 Correct 58 ms 15864 KB Output is correct
10 Incorrect 78 ms 18040 KB Output isn't correct

Subtask #3
18.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2091 ms 231748 KB Time limit exceeded
2 Correct 319 ms 53848 KB Output is correct
3 Correct 472 ms 73464 KB Output is correct
4 Execution timed out 2094 ms 286820 KB Time limit exceeded
5 Execution timed out 2107 ms 257912 KB Time limit exceeded
6 Incorrect 631 ms 96888 KB Output isn't correct
7 Execution timed out 2085 ms 223668 KB Time limit exceeded
8 Execution timed out 2076 ms 186360 KB Time limit exceeded
9 Execution timed out 2102 ms 230336 KB Time limit exceeded
10 Correct 981 ms 129100 KB Output is correct
11 Execution timed out 2099 ms 266348 KB Time limit exceeded
12 Execution timed out 2062 ms 214704 KB Time limit exceeded
13 Correct 535 ms 80740 KB Output is correct
14 Correct 393 ms 60764 KB Output is correct
15 Correct 675 ms 102520 KB Output is correct
16 Execution timed out 2079 ms 224172 KB Time limit exceeded
17 Execution timed out 2057 ms 209104 KB Time limit exceeded
18 Correct 516 ms 73740 KB Output is correct
19 Correct 324 ms 53880 KB Output is correct
20 Correct 562 ms 89976 KB Output is correct