Guest User

Untitled

a guest
Oct 18th, 2019
950
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void solve()
  6. {
  7.     int n;
  8.     cin>>n;
  9.     string s;
  10.     cin>>s;
  11.     vector < vector <int> > dp(n,vector <int> (7,0));
  12.     dp[0][0]=s[0]=='0';
  13.     dp[0][1]=s[0]=='1';
  14.     for(int i=1;i<n;i++){
  15.         dp[i]=dp[i-1];
  16.         if(s[i]=='1'){
  17.             dp[i][1]++;
  18.             if(dp[i-1][0]!=0||dp[i-1][2]!=0)
  19.                 dp[i][2]=max(dp[i-1][0]+1,dp[i-1][2]+1);
  20.             if(dp[i-1][5]!=0||dp[i-1][3]!=0)
  21.                 dp[i][5]=max(dp[i-1][3]+1,dp[i-1][5]+1);
  22.             if(dp[i-1][6]!=0||dp[i-1][4]!=0)
  23.                 dp[i][6]=max(dp[i-1][6]+1,dp[i-1][4]+1);
  24.         }
  25.         else{
  26.             dp[i][0]++;
  27.             if(dp[i-1][3]!=0||dp[i-1][1]!=0)
  28.                 dp[i][3]=max(dp[i-1][3]+1,dp[i-1][1]+1);
  29.             if(dp[i-1][4]!=0||dp[i-1][2]!=0)
  30.                 dp[i][4]=max(dp[i-1][4]+1,dp[i-1][2]+1);
  31.         }
  32.     }
  33.     cout<<*max_element(begin(dp.back()),end(dp.back()));
  34. }
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.     int t;
  42.     t=1;
  43.     //cin>>t;
  44.     while(t--){
  45.         solve();
  46.     }
  47.     return 0;
  48. }
Add Comment
Please, Sign In to add comment