oj.uz

답안 #256374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256374 2020-08-02T15:43:17 Z shayan_p Vim (BOI13_vim) C++14
75.6111 / 100
 2000 ms 305068 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(nxt[ poses[i] ][8] + 10 < j)
	return inf;
    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] );
    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 10 ms 7936 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 6 ms 7296 KB Output is correct
4 Correct 8 ms 7552 KB Output is correct
5 Correct 16 ms 8320 KB Output is correct
6 Correct 8 ms 7552 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 6 ms 6912 KB Output is correct
9 Correct 4 ms 6912 KB Output is correct
10 Correct 4 ms 6912 KB Output is correct
11 Correct 4 ms 6860 KB Output is correct
12 Correct 4 ms 6912 KB Output is correct
13 Correct 10 ms 7936 KB Output is correct
14 Correct 8 ms 7552 KB Output is correct
15 Correct 6 ms 7296 KB Output is correct
16 Correct 7 ms 7492 KB Output is correct
17 Correct 12 ms 7424 KB Output is correct
18 Correct 7 ms 7380 KB Output is correct
19 Incorrect 13 ms 7680 KB Output isn't correct
20 Correct 13 ms 7680 KB Output is correct
21 Correct 8 ms 7552 KB Output is correct
22 Correct 14 ms 8320 KB Output is correct
23 Correct 10 ms 7680 KB Output is correct
24 Correct 12 ms 7552 KB Output is correct
25 Correct 6 ms 7296 KB Output is correct
26 Correct 6 ms 7168 KB Output is correct
27 Correct 8 ms 7424 KB Output is correct
28 Correct 12 ms 7552 KB Output is correct
29 Correct 9 ms 7680 KB Output is correct
30 Correct 8 ms 7552 KB Output is correct
31 Correct 7 ms 7424 KB Output is correct
32 Correct 6 ms 7200 KB Output is correct
33 Correct 7 ms 7168 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 8 ms 7552 KB Output is correct
36 Correct 13 ms 7680 KB Output is correct

Subtask #2
9.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 12536 KB Output is correct
2 Correct 48 ms 13912 KB Output is correct
3 Correct 31 ms 11256 KB Output is correct
4 Correct 40 ms 12536 KB Output is correct
5 Correct 169 ms 27128 KB Output is correct
6 Correct 771 ms 91384 KB Output is correct
7 Correct 147 ms 27384 KB Output is correct
8 Correct 59 ms 14840 KB Output is correct
9 Correct 48 ms 13816 KB Output is correct
10 Incorrect 69 ms 16632 KB Output isn't correct

Subtask #3
18.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2102 ms 249248 KB Time limit exceeded
2 Correct 287 ms 46456 KB Output is correct
3 Correct 414 ms 64880 KB Output is correct
4 Execution timed out 2100 ms 291832 KB Time limit exceeded
5 Execution timed out 2111 ms 258040 KB Time limit exceeded
6 Incorrect 550 ms 83196 KB Output isn't correct
7 Execution timed out 2096 ms 274168 KB Time limit exceeded
8 Execution timed out 2064 ms 230064 KB Time limit exceeded
9 Execution timed out 2111 ms 272980 KB Time limit exceeded
10 Correct 800 ms 114552 KB Output is correct
11 Execution timed out 2107 ms 305068 KB Time limit exceeded
12 Execution timed out 2113 ms 254076 KB Time limit exceeded
13 Correct 453 ms 70904 KB Output is correct
14 Correct 308 ms 52088 KB Output is correct
15 Correct 552 ms 81568 KB Output is correct
16 Execution timed out 2113 ms 269348 KB Time limit exceeded
17 Execution timed out 2112 ms 238180 KB Time limit exceeded
18 Correct 407 ms 65016 KB Output is correct
19 Correct 286 ms 46348 KB Output is correct
20 Correct 457 ms 71800 KB Output is correct