fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string x;
  4. long long int dp[200005][3][2];
  5. long long int f(int i,int m,int ff)
  6. {
  7.     if(i==(x.size()-1))
  8.     {
  9.         if(ff==0)
  10.         {
  11.             if( (x[i]-48)%3==0 )
  12.             return 1LL;
  13.             else
  14.             return 0LL;
  15.         }
  16.         else
  17.         {
  18.             m=  ( (m*10) + (int)(x[i]-48))%3;
  19.             if(m==0)
  20.             return 1LL;
  21.             else
  22.             return 0LL;
  23.         }
  24.     }
  25.  
  26.     if(dp[i][m][ff] != -1)
  27.     return dp[i][m][ff];
  28.  
  29.     long long int ans=0;
  30.  
  31.  
  32.         m=  ( (m*10) + (int)(x[i]-48))%3;
  33.         if(m==0)
  34.         {
  35.             ans = max( (1LL+f(i+1,0,0)) ,f(i+1,m,1));
  36.         }
  37.         else
  38.         {
  39.             ans = max( f(i+1,0,0),  f(i+1,m,1) );
  40.         }
  41.  
  42.     return dp[i][m][ff]=ans;
  43. }
  44. int main()
  45. {
  46.     std::ios::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.     cout.tie(NULL);
  49.     cin>>x;
  50.     memset(dp,-1,sizeof(dp));
  51.     cout<<f(0,0,0)<<endl;
  52. 	return 0;
  53. }
Runtime error #stdin #stdout 0.01s 24644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/G1pI7J
language:
C++14 (clang 8.0)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!