Submission #378432

# Submission time Handle Problem Language Result Execution time Memory
378432 2021-03-16T18:22:08 Z YJU Vim (BOI13_vim) C++14
51 / 100
2000 ms 460412 KB
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=7e4+5;
const ll INF=(1LL<<60);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define lwb lower_bound

ll nxt[N][11],e[N];
unordered_map<ll,ll> dp[N];
string s;
vector<ll> loc;
ll n,m;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s;
	REP(j,10)nxt[n][j]=n;
	for(int i=n-1;i>=0;i--){
		REP(j,10)nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i]-'a']=i;
        e[i]=(s[i+1]=='e'?e[i+1]:i+1);
        if(s[i]=='e')loc.pb(i);
	}
	reverse(loc.begin(),loc.end());
	m=loc.size();
	REP(i,n)dp[m][i]=0;
	for(int i=m-1;i>=0;i--){
        for(int j=n-1;j>=0;j--){
			dp[i][j]=INF;
			if(s[j]=='e')continue;
			ll ii=lwb(loc.begin(),loc.end(),j)-loc.begin();
			if(j>loc[i])dp[i][j]=min(dp[i][j],dp[ii][e[loc[i]]]+(j-loc[i]));
			for(int k=0;k<10;k++){
				if(k=='e'-'a'||nxt[j+1][k]==n)continue;
				dp[i][j]=min(dp[i][j],dp[i][nxt[j+1][k]]+2);
			}
        }
	}
	cout<<dp[0][0]+m<<"\n";
	//REP(i,m)REP(j,n)cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 33 ms 10220 KB Output is correct
2 Correct 20 ms 7680 KB Output is correct
3 Correct 16 ms 6764 KB Output is correct
4 Correct 22 ms 7660 KB Output is correct
5 Correct 24 ms 7788 KB Output is correct
6 Correct 33 ms 9452 KB Output is correct
7 Correct 31 ms 8812 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 33 ms 10220 KB Output is correct
14 Correct 20 ms 7660 KB Output is correct
15 Correct 16 ms 6764 KB Output is correct
16 Correct 20 ms 7660 KB Output is correct
17 Correct 25 ms 7532 KB Output is correct
18 Correct 18 ms 6764 KB Output is correct
19 Correct 15 ms 6636 KB Output is correct
20 Correct 17 ms 6764 KB Output is correct
21 Correct 21 ms 7532 KB Output is correct
22 Correct 24 ms 7808 KB Output is correct
23 Correct 17 ms 6508 KB Output is correct
24 Correct 18 ms 6524 KB Output is correct
25 Correct 18 ms 6508 KB Output is correct
26 Correct 18 ms 7020 KB Output is correct
27 Correct 29 ms 8300 KB Output is correct
28 Correct 38 ms 9592 KB Output is correct
29 Correct 29 ms 8812 KB Output is correct
30 Correct 19 ms 7040 KB Output is correct
31 Correct 18 ms 6508 KB Output is correct
32 Correct 20 ms 6892 KB Output is correct
33 Correct 21 ms 7148 KB Output is correct
34 Correct 26 ms 7916 KB Output is correct
35 Correct 28 ms 8556 KB Output is correct
36 Correct 34 ms 8812 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2107 ms 449932 KB Time limit exceeded
2 Execution timed out 2114 ms 362732 KB Time limit exceeded
3 Correct 1033 ms 175920 KB Output is correct
4 Execution timed out 2118 ms 451432 KB Time limit exceeded
5 Execution timed out 2111 ms 350956 KB Time limit exceeded
6 Execution timed out 2111 ms 298860 KB Time limit exceeded
7 Execution timed out 2115 ms 416636 KB Time limit exceeded
8 Execution timed out 2104 ms 396132 KB Time limit exceeded
9 Execution timed out 2071 ms 358124 KB Time limit exceeded
10 Execution timed out 2120 ms 372752 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Execution timed out 2108 ms 324508 KB Time limit exceeded
2 Execution timed out 2109 ms 380660 KB Time limit exceeded
3 Execution timed out 2066 ms 337228 KB Time limit exceeded
4 Execution timed out 2080 ms 441060 KB Time limit exceeded
5 Execution timed out 2114 ms 366868 KB Time limit exceeded
6 Execution timed out 2116 ms 447716 KB Time limit exceeded
7 Execution timed out 2127 ms 416168 KB Time limit exceeded
8 Execution timed out 2122 ms 380940 KB Time limit exceeded
9 Execution timed out 2093 ms 444896 KB Time limit exceeded
10 Execution timed out 2129 ms 460412 KB Time limit exceeded
11 Execution timed out 2131 ms 452944 KB Time limit exceeded
12 Execution timed out 2125 ms 366800 KB Time limit exceeded
13 Execution timed out 2127 ms 390396 KB Time limit exceeded
14 Execution timed out 2119 ms 424784 KB Time limit exceeded
15 Execution timed out 2119 ms 404388 KB Time limit exceeded
16 Execution timed out 2107 ms 372484 KB Time limit exceeded
17 Execution timed out 2109 ms 324372 KB Time limit exceeded
18 Execution timed out 2123 ms 345208 KB Time limit exceeded
19 Execution timed out 2125 ms 385396 KB Time limit exceeded
20 Execution timed out 2099 ms 361332 KB Time limit exceeded