oj.uz

Submission #378422

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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