Submission #501768

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define BE(c) c.begin(),c.end()
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long double ld;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
const ut INF=1<<30;
const LL p=7+1e+9;
const int SIZE=5+1e+3;
using namespace std;
string s;
bool checked[SIZE][2];
int DP[SIZE][2];
int solve(int x,bool isUp){
	if(x==s.size()){
		if(isUp) return -INF;
		return 0;
	} 
	if(checked[x][isUp]) return DP[x][isUp];
	checked[x][isUp]=true;
	if(s[x]=='0'){
		if(isUp) DP[x][isUp]=solve(x+1,true);
		else DP[x][isUp]=max(solve(x+1,true),solve(x+1,false)+1);
	} 
	else if(s[x]=='9'){
		if(isUp) DP[x][isUp]=max(solve(x+1,true)+1,solve(x+1,false));
		else DP[x][isUp]=solve(x+1,false);
	}
	else{
		DP[x][isUp]=max(solve(x+1,true),solve(x+1,false));
	}
	return DP[x][isUp];
}
int main() {
	cin >> s;
	cout << max(solve(0,0),solve(0,1)) << endl;
	// your code goes here
	return 0;
}

Submission Info

Judge Result