Submission #3635617

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
Int dp[2][111];
signed main(){
  string s;
  cin>>s;

  Int n=s.size();
  reverse(s.begin(),s.end());
  memset(dp,-1,sizeof(dp));

  dp[0][0]=0;
  for(Int i=0;i<n;i++){
    //cout<<dp[0][i]<<" "<<dp[1][i]<<endl;
    for(Int j=0;j<10;j++){      
      Int a=s[i]-'0';
      for(Int b=0;b<2;b++){
        if(dp[b][i]<0) continue;
        Int x=(j+a+b)%10,k=(j+a+b)/10;
        chmax(dp[k][i+1],dp[b][i]+(j==a&&a==x));        
      }
    }
  }
  
  cout<<max(dp[0][n],dp[1][n])<<endl;
  return 0;
}

Submission Info

Judge Result