fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. #define endl '\n'
  10. #define BIT(i) ((1 << i))
  11. void maximize(int &x, int y)
  12. {
  13.     if(x < y) x = y;
  14. }
  15. const int maxn = 5e5 + 5;
  16. int n;
  17. int sum[maxn] , pre[maxn];
  18. int a[maxn];
  19.  
  20. void solve(){
  21.     cin >> n;
  22.     for(int i=1; i<=n; i++){
  23.         char x;
  24.         cin >> x;
  25.         int tmp = int(x) - int('0');
  26.         a[i] = tmp;
  27.         sum[i] = sum[i - 1] + (tmp ^ 1);
  28.  
  29.     }
  30.     for(int i=1; i<=n; i++){
  31.         if(a[i] == 1)
  32.         {
  33.             int j = i - 1;
  34.             while(j >= 0)
  35.             {
  36.                 if(a[j] == 1) break;
  37.                 pre[sum[j]] = i;
  38.                 j--;
  39.             }
  40.         }
  41.     }
  42.     int res = n - sum[n];
  43.     for(int val=1; val<=sum[n]; val++)
  44.     {
  45.         int nxt = pre[val];
  46.         if(nxt == 0) break;
  47.         int ans = 0;
  48.         while(sum[n] - sum[nxt] >= val)
  49.         {
  50.             if(pre[sum[nxt] + val] == 0)
  51.             {
  52.                 ans++;
  53.                 break;
  54.             }
  55.             ans++;
  56.             nxt = pre[sum[nxt] + val];
  57.         }
  58.         if(ans == 0) break;
  59.         maximize(res , ans + val * (ans + 1));
  60.     }
  61.     cout << res;
  62. }
  63.  
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(0);
  68.     cout.tie(0);
  69.     #define code code
  70. //    freopen("code.INP","r",stdin);
  71. //    freopen("code.OUT","w",stdout);
  72.     solve();
  73.     return 0;
  74. }
  75.  
  76.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/GwLXq6
language:
C++14 (clang 8.0)
created:
16 hours 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!