Submission #378423

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378423	2021-03-16T18:05:25 Z	YJU	Vim (BOI13_vim)	C++14	0 / 100	26 ms	21548 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<<30);
#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];
map<ll,ll> dp[N];
string s;
vector<ll> loc;
ll n,m;

ll f(ll have,ll id){
    if(have==m)return 0;
    if(dp[have].find(id)!=dp[have].end())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();
	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

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	8 ms	7276 KB	Execution killed with signal 11
2	Runtime error	8 ms	7276 KB	Execution killed with signal 11
3	Runtime error	8 ms	7276 KB	Execution killed with signal 11
4	Runtime error	8 ms	7276 KB	Execution killed with signal 11
5	Runtime error	8 ms	7276 KB	Execution killed with signal 11
6	Runtime error	8 ms	7276 KB	Execution killed with signal 11
7	Runtime error	8 ms	7276 KB	Execution killed with signal 11
8	Runtime error	8 ms	7148 KB	Execution killed with signal 11
9	Runtime error	8 ms	7148 KB	Execution killed with signal 11
10	Runtime error	8 ms	7148 KB	Execution killed with signal 11
11	Runtime error	8 ms	7148 KB	Execution killed with signal 11
12	Runtime error	8 ms	7148 KB	Execution killed with signal 11
13	Runtime error	8 ms	7276 KB	Execution killed with signal 11
14	Runtime error	8 ms	7276 KB	Execution killed with signal 11
15	Runtime error	10 ms	7276 KB	Execution killed with signal 11
16	Runtime error	8 ms	7276 KB	Execution killed with signal 11
17	Runtime error	9 ms	7296 KB	Execution killed with signal 11
18	Runtime error	8 ms	7424 KB	Execution killed with signal 11
19	Runtime error	9 ms	7268 KB	Execution killed with signal 11
20	Runtime error	8 ms	7276 KB	Execution killed with signal 11
21	Runtime error	8 ms	7276 KB	Execution killed with signal 11
22	Runtime error	8 ms	7276 KB	Execution killed with signal 11
23	Runtime error	8 ms	7276 KB	Execution killed with signal 11
24	Runtime error	10 ms	7276 KB	Execution killed with signal 11
25	Runtime error	8 ms	7276 KB	Execution killed with signal 11
26	Runtime error	8 ms	7276 KB	Execution killed with signal 11
27	Runtime error	8 ms	7276 KB	Execution killed with signal 11
28	Runtime error	8 ms	7276 KB	Execution killed with signal 11
29	Runtime error	8 ms	7276 KB	Execution killed with signal 11
30	Runtime error	8 ms	7296 KB	Execution killed with signal 11
31	Runtime error	8 ms	7276 KB	Execution killed with signal 11
32	Runtime error	8 ms	7276 KB	Execution killed with signal 11
33	Runtime error	8 ms	7224 KB	Execution killed with signal 11
34	Runtime error	9 ms	7276 KB	Execution killed with signal 11
35	Runtime error	9 ms	7276 KB	Execution killed with signal 11
36	Runtime error	9 ms	7276 KB	Execution killed with signal 11

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	12 ms	8172 KB	Execution killed with signal 11
2	Runtime error	11 ms	8172 KB	Execution killed with signal 11
3	Runtime error	10 ms	7788 KB	Execution killed with signal 11
4	Runtime error	9 ms	8172 KB	Execution killed with signal 11
5	Runtime error	9 ms	8172 KB	Execution killed with signal 11
6	Runtime error	9 ms	8300 KB	Execution killed with signal 11
7	Runtime error	9 ms	8172 KB	Execution killed with signal 11
8	Runtime error	9 ms	8172 KB	Execution killed with signal 11
9	Runtime error	9 ms	8172 KB	Execution killed with signal 11
10	Runtime error	9 ms	8172 KB	Execution killed with signal 11

Subtask #3
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	20 ms	19308 KB	Execution killed with signal 11
2	Runtime error	20 ms	19048 KB	Execution killed with signal 11
3	Runtime error	20 ms	19436 KB	Execution killed with signal 11
4	Runtime error	22 ms	21548 KB	Execution killed with signal 11
5	Runtime error	22 ms	21292 KB	Execution killed with signal 11
6	Runtime error	21 ms	19940 KB	Execution killed with signal 11
7	Runtime error	21 ms	20200 KB	Execution killed with signal 11
8	Runtime error	26 ms	20328 KB	Execution killed with signal 11
9	Runtime error	22 ms	20476 KB	Execution killed with signal 11
10	Runtime error	22 ms	20580 KB	Execution killed with signal 11
11	Runtime error	22 ms	21548 KB	Execution killed with signal 11
12	Runtime error	22 ms	21292 KB	Execution killed with signal 11
13	Runtime error	22 ms	20908 KB	Execution killed with signal 11
14	Runtime error	21 ms	21164 KB	Execution killed with signal 11
15	Runtime error	22 ms	21420 KB	Execution killed with signal 11
16	Runtime error	19 ms	19180 KB	Execution killed with signal 11
17	Runtime error	20 ms	19308 KB	Execution killed with signal 11
18	Runtime error	19 ms	19436 KB	Execution killed with signal 11
19	Runtime error	20 ms	19048 KB	Execution killed with signal 11
20	Runtime error	20 ms	19304 KB	Execution killed with signal 11

Submission #378423

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