답안 #378422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378422	2021-03-16T18:01:39 Z	YJU	Vim (BOI13_vim)	C++14	0 / 100	275 ms	524292 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/30+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;
}

Subtask #1
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	272 ms	524292 KB	Execution killed with signal 9
2	Runtime error	262 ms	524292 KB	Execution killed with signal 9
3	Runtime error	267 ms	524292 KB	Execution killed with signal 9
4	Runtime error	268 ms	524292 KB	Execution killed with signal 9
5	Runtime error	271 ms	524292 KB	Execution killed with signal 9
6	Runtime error	262 ms	524288 KB	Execution killed with signal 9
7	Runtime error	270 ms	524292 KB	Execution killed with signal 9
8	Runtime error	265 ms	524292 KB	Execution killed with signal 9
9	Runtime error	263 ms	524292 KB	Execution killed with signal 9
10	Runtime error	265 ms	524292 KB	Execution killed with signal 9
11	Runtime error	273 ms	524292 KB	Execution killed with signal 9
12	Runtime error	266 ms	524292 KB	Execution killed with signal 9
13	Runtime error	271 ms	524292 KB	Execution killed with signal 9
14	Runtime error	270 ms	524292 KB	Execution killed with signal 9
15	Runtime error	267 ms	524292 KB	Execution killed with signal 9
16	Runtime error	267 ms	524292 KB	Execution killed with signal 9
17	Runtime error	269 ms	524292 KB	Execution killed with signal 9
18	Runtime error	272 ms	524292 KB	Execution killed with signal 9
19	Runtime error	268 ms	524292 KB	Execution killed with signal 9
20	Runtime error	269 ms	524292 KB	Execution killed with signal 9
21	Runtime error	268 ms	524292 KB	Execution killed with signal 9
22	Runtime error	266 ms	524292 KB	Execution killed with signal 9
23	Runtime error	273 ms	524292 KB	Execution killed with signal 9
24	Runtime error	268 ms	524292 KB	Execution killed with signal 9
25	Runtime error	266 ms	524292 KB	Execution killed with signal 9
26	Runtime error	263 ms	524288 KB	Execution killed with signal 9
27	Runtime error	267 ms	524292 KB	Execution killed with signal 9
28	Runtime error	262 ms	524292 KB	Execution killed with signal 9
29	Runtime error	267 ms	524292 KB	Execution killed with signal 9
30	Runtime error	268 ms	524292 KB	Execution killed with signal 9
31	Runtime error	266 ms	524292 KB	Execution killed with signal 9
32	Runtime error	261 ms	524292 KB	Execution killed with signal 9
33	Runtime error	267 ms	524292 KB	Execution killed with signal 9
34	Runtime error	268 ms	524292 KB	Execution killed with signal 9
35	Runtime error	266 ms	524292 KB	Execution killed with signal 9
36	Runtime error	269 ms	524292 KB	Execution killed with signal 9

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	271 ms	524292 KB	Execution killed with signal 9
2	Runtime error	275 ms	524292 KB	Execution killed with signal 9
3	Runtime error	270 ms	524292 KB	Execution killed with signal 9
4	Runtime error	265 ms	524292 KB	Execution killed with signal 9
5	Runtime error	270 ms	524292 KB	Execution killed with signal 9
6	Runtime error	266 ms	524292 KB	Execution killed with signal 9
7	Runtime error	262 ms	524292 KB	Execution killed with signal 9
8	Runtime error	261 ms	524292 KB	Execution killed with signal 9
9	Runtime error	263 ms	524292 KB	Execution killed with signal 9
10	Runtime error	263 ms	524292 KB	Execution killed with signal 9

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	261 ms	524292 KB	Execution killed with signal 9
2	Runtime error	270 ms	524292 KB	Execution killed with signal 9
3	Runtime error	268 ms	524292 KB	Execution killed with signal 9
4	Runtime error	264 ms	524292 KB	Execution killed with signal 9
5	Runtime error	266 ms	524292 KB	Execution killed with signal 9
6	Runtime error	269 ms	524292 KB	Execution killed with signal 9
7	Runtime error	265 ms	524292 KB	Execution killed with signal 9
8	Runtime error	265 ms	524292 KB	Execution killed with signal 9
9	Runtime error	267 ms	524292 KB	Execution killed with signal 9
10	Runtime error	264 ms	524292 KB	Execution killed with signal 9
11	Runtime error	264 ms	524292 KB	Execution killed with signal 9
12	Runtime error	262 ms	524292 KB	Execution killed with signal 9
13	Runtime error	262 ms	524288 KB	Execution killed with signal 9
14	Runtime error	266 ms	524292 KB	Execution killed with signal 9
15	Runtime error	260 ms	524288 KB	Execution killed with signal 9
16	Runtime error	269 ms	524292 KB	Execution killed with signal 9
17	Runtime error	267 ms	524292 KB	Execution killed with signal 9
18	Runtime error	264 ms	524292 KB	Execution killed with signal 9
19	Runtime error	262 ms	524292 KB	Execution killed with signal 9
20	Runtime error	272 ms	524292 KB	Execution killed with signal 9

답안 #378422

Compilation message

Subtask #1 0 / 50.0

Subtask #2 0 / 10.0

Subtask #3 0 / 40.0

Subtask #1
0 / 50.0

Subtask #2
0 / 10.0

Subtask #3
0 / 40.0