fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define vi vector<int>
  6. #define pb push_back
  7. #define fr_z(start,end) for(int z=start;z<end;z++)
  8. #define fr_o(start,end) for(int o=start;o<end;o++)
  9. #define all(m) m.begin(),m.end()
  10. #define mp make_pair
  11. #define fa_io std::ios::sync_with_stdio(false); cin.tie(NULL)
  12.  
  13. pair<int,int> totct[100000];
  14. int len[100000],prv[100000];
  15.  
  16. int main()
  17. {
  18.     fa_io;
  19.  
  20.     int t,n;
  21.     string s;
  22.     cin>>t;
  23.     while(t--)
  24.     {
  25.         cin>>n;
  26.         cin>>s;
  27.         fr_z(0,n)
  28.             len[z]=0,prv[z]=-1;
  29.         totct[0]=(s[0]=='0')?mp(1,0):mp(0,1);
  30.         fr_z(1,n)
  31.             totct[z]=s[z]=='0'?mp(totct[z-1].first+1,totct[z-1].second):mp(totct[z-1].first,totct[z-1].second+1);
  32.         fr_z(0,n)
  33.         {
  34.             int tz=totct[z].first,to=totct[z].second;
  35.             //cout<<z<<'-'<<tz<<
  36.             fr_o(0,z+1)
  37.             {
  38.                 if(to>tz && len[z]<tz+to)
  39.                     len[z]=tz+to,prv[z]=o;
  40.                 //cout<<tz<<'-'<<to<<'\n';
  41.                 s[o]=='0'?tz--:to--;
  42.             }
  43.         }
  44.         int z=n-1,j,u;
  45.         /*cout<<'\n';
  46.         fr_z(0,n)
  47.             cout<<setw(4)<<len[z]<<' ';*/
  48.         int sm=0;
  49.         while(z>=0)
  50.         {
  51.             if(!len[z])
  52.             {
  53.                 z--;
  54.                 continue;
  55.             }
  56.             u=z-1;
  57.             bool i=true;
  58.             for(u=z-1;u>z-len[z];u--)
  59.                 if(len[u]>=len[z])
  60.                 {
  61.                     i=false;
  62.                     break;
  63.                 }
  64.             if(i)
  65.                 fr_o(z-len[z]+1,z)
  66.                     len[o]=0;
  67.             else
  68.                 len[z]=0;
  69.             z--;
  70.         }
  71.         /*cout<<'\n';
  72.         fr_z(0,n)
  73.             cout<<setw(4)<<len[z]<<' ';
  74.         cout<<'\n';
  75.         fr_z(0,n)
  76.             cout<<setw(4)<<prv[z]<<' ';*/
  77.         cout<<accumulate(len,len+n,0)<<'\n';
  78.     }
  79.  
  80.     return 0;
  81. }
Runtime error #stdin #stdout 0s 17624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OsZ2yU
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!