Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- void solve()
- {
- int n;
- cin>>n;
- string s;
- cin>>s;
- vector < vector <int> > dp(n,vector <int> (7,0));
- dp[0][0]=s[0]=='0';
- dp[0][1]=s[0]=='1';
- for(int i=1;i<n;i++){
- dp[i]=dp[i-1];
- if(s[i]=='1'){
- dp[i][1]++;
- if(dp[i-1][0]!=0||dp[i-1][2]!=0)
- dp[i][2]=max(dp[i-1][0]+1,dp[i-1][2]+1);
- if(dp[i-1][5]!=0||dp[i-1][3]!=0)
- dp[i][5]=max(dp[i-1][3]+1,dp[i-1][5]+1);
- if(dp[i-1][6]!=0||dp[i-1][4]!=0)
- dp[i][6]=max(dp[i-1][6]+1,dp[i-1][4]+1);
- }
- else{
- dp[i][0]++;
- if(dp[i-1][3]!=0||dp[i-1][1]!=0)
- dp[i][3]=max(dp[i-1][3]+1,dp[i-1][1]+1);
- if(dp[i-1][4]!=0||dp[i-1][2]!=0)
- dp[i][4]=max(dp[i-1][4]+1,dp[i-1][2]+1);
- }
- }
- cout<<*max_element(begin(dp.back()),end(dp.back()));
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- t=1;
- //cin>>t;
- while(t--){
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment