답안 #378420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378420 2021-03-16T18:00:00 Z YJU Vim (BOI13_vim) C++14
50 / 100
831 ms 524288 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 SN=N/100+4;
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],dp[SN][N],e[N];
string s;
vector<ll> loc;
ll n,m;

ll f(ll have,ll id){
    if(have==m)return 0;
    if(dp[have][id]!=-1)return dp[have][id];
    dp[have][id]=INF;
	if(id>loc[have]){
		ll nhave=lwb(loc.begin(),loc.end(),id)-loc.begin();
		dp[have][id]=min(dp[have][id],f(nhave,e[loc[have]])+(id-loc[have]));
	}
	REP(j,10){
		if(j=='e'-'a'||nxt[id+1][j]==n)continue;
		dp[have][id]=min(dp[have][id],f(have,nxt[id+1][j])+2);
	}
	return dp[have][id];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	memset(dp,-1,sizeof(dp));
	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);
	}
	sort(loc.begin(),loc.end());
	m=loc.size();
	assert(m<SN);
	cout<<f(0,0)+m<<"\n";
	//REP(i,m)REP(j,n)cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 386156 KB Output is correct
2 Correct 200 ms 386156 KB Output is correct
3 Correct 200 ms 386156 KB Output is correct
4 Correct 199 ms 386156 KB Output is correct
5 Correct 199 ms 386156 KB Output is correct
6 Correct 202 ms 386156 KB Output is correct
7 Correct 199 ms 386156 KB Output is correct
8 Correct 198 ms 386156 KB Output is correct
9 Correct 200 ms 386156 KB Output is correct
10 Correct 196 ms 386284 KB Output is correct
11 Correct 198 ms 386156 KB Output is correct
12 Correct 197 ms 386144 KB Output is correct
13 Correct 199 ms 386284 KB Output is correct
14 Correct 199 ms 386284 KB Output is correct
15 Correct 200 ms 386284 KB Output is correct
16 Correct 198 ms 386284 KB Output is correct
17 Correct 202 ms 386156 KB Output is correct
18 Correct 200 ms 386156 KB Output is correct
19 Correct 199 ms 386284 KB Output is correct
20 Correct 197 ms 386156 KB Output is correct
21 Correct 202 ms 386284 KB Output is correct
22 Correct 198 ms 386156 KB Output is correct
23 Correct 201 ms 386284 KB Output is correct
24 Correct 198 ms 386156 KB Output is correct
25 Correct 199 ms 386156 KB Output is correct
26 Correct 200 ms 386156 KB Output is correct
27 Correct 204 ms 386412 KB Output is correct
28 Correct 200 ms 386156 KB Output is correct
29 Correct 199 ms 386156 KB Output is correct
30 Correct 201 ms 386156 KB Output is correct
31 Correct 202 ms 386156 KB Output is correct
32 Correct 216 ms 386144 KB Output is correct
33 Correct 203 ms 386312 KB Output is correct
34 Correct 199 ms 386156 KB Output is correct
35 Correct 197 ms 386156 KB Output is correct
36 Correct 202 ms 386284 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 768 ms 524288 KB Execution killed with signal 6
2 Runtime error 823 ms 524288 KB Execution killed with signal 6
3 Runtime error 768 ms 524288 KB Execution killed with signal 6
4 Runtime error 768 ms 524288 KB Execution killed with signal 6
5 Runtime error 768 ms 524288 KB Execution killed with signal 6
6 Runtime error 767 ms 524288 KB Execution killed with signal 6
7 Runtime error 789 ms 524288 KB Execution killed with signal 6
8 Runtime error 757 ms 524288 KB Execution killed with signal 6
9 Runtime error 766 ms 524288 KB Execution killed with signal 6
10 Runtime error 776 ms 524288 KB Execution killed with signal 6
# 결과 실행 시간 메모리 Grader output
1 Runtime error 831 ms 524288 KB Execution killed with signal 6
2 Runtime error 789 ms 524288 KB Execution killed with signal 6
3 Runtime error 780 ms 524288 KB Execution killed with signal 6
4 Runtime error 765 ms 524288 KB Execution killed with signal 6
5 Runtime error 775 ms 524288 KB Execution killed with signal 6
6 Runtime error 786 ms 524288 KB Execution killed with signal 6
7 Runtime error 771 ms 524288 KB Execution killed with signal 6
8 Runtime error 775 ms 524288 KB Execution killed with signal 6
9 Runtime error 788 ms 524288 KB Execution killed with signal 6
10 Runtime error 780 ms 524288 KB Execution killed with signal 6
11 Runtime error 805 ms 524288 KB Execution killed with signal 6
12 Runtime error 799 ms 524288 KB Execution killed with signal 6
13 Runtime error 800 ms 524288 KB Execution killed with signal 6
14 Runtime error 799 ms 524288 KB Execution killed with signal 6
15 Runtime error 776 ms 524288 KB Execution killed with signal 6
16 Runtime error 783 ms 524288 KB Execution killed with signal 6
17 Runtime error 808 ms 524288 KB Execution killed with signal 6
18 Runtime error 789 ms 524288 KB Execution killed with signal 6
19 Runtime error 774 ms 524288 KB Execution killed with signal 6
20 Runtime error 761 ms 524288 KB Execution killed with signal 6