fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. #define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
  10. #define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
  11. template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
  12. template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
  13.  
  14. using namespace std;
  15.  
  16. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  17. #define rand rd
  18.  
  19. long long Rand(long long l , long long h){
  20. 	assert(l <= h);
  21. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  22. }
  23.  
  24.  
  25. //////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////
  26.  
  27. const int MAX = 5e5 + 5;
  28. int n;
  29. int sum[MAX] , pre[MAX];
  30. int a[MAX];
  31.  
  32. void INP(){
  33.     cin >> n;
  34.     forr(i , 1 , n , 1){
  35.         char x;
  36.         cin >> x;
  37.         int tmp = int(x) - int('0');
  38.         a[i] = tmp;
  39.         sum[i] = sum[i - 1] + (tmp ^ 1);
  40.  
  41.     }
  42.     forr(i , 1 , n , 1){
  43.         if(a[i] == 1){
  44.             //cout << i << ' ';
  45.             int j = i - 1;
  46.             while(j >= 0){
  47.                 if(a[j] == 1) break;
  48.                 pre[sum[j]] = i;
  49.                 j--;
  50.             }
  51.             //cout << j << endl;
  52.         }
  53.     }
  54.     int res = n - sum[n];
  55.     forr(num_0 , 1 , sum[n] , 1){
  56.         int nxt = pre[num_0];
  57.         //cout << nxt << endl;
  58.         if(nxt == 0) break;
  59.         int ans = 0;
  60.         while(sum[n] - sum[nxt] >= num_0){
  61.             if(pre[sum[nxt] + num_0] == 0){
  62.                 ans++;
  63.                 break;
  64.             }
  65.             ans++;
  66.             nxt = pre[sum[nxt] + num_0];
  67.         }
  68.         if(ans == 0) break;
  69.         maximize(res , ans + num_0 * (ans + 1));
  70.         //cout << num_0 << ' ' << ans << endl;
  71.     }
  72.     cout << res;
  73. }
  74.  
  75. int main()
  76. {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80.     #define TASK ""
  81.     //freopen(TASK".inp" , "r" , stdin);
  82.     //freopen(TASK".out" , "w" , stdout);
  83.     INP();
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HNHP4O
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!