Submission #1686548

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <chrono>
#include <numeric>

using namespace std;

long long n;
char s[500001];
long long z[500001];
vector<vector<long long>> v;

long long solve(const vector<long long> &a) {
  size_t a_len = a.size();
  long long l, r1, r2, l_prev, r1_prev, r2_prev;
  l_prev = 0;
  r1_prev = 0;
  r2_prev = a[0];
  for (long long i=1;i<(a_len-1);i++) {
    if (a[i] > 1) {
      // l:left pattern O
      l = max(l_prev + a[i] - 1, max(r1_prev, r2_prev));
      // r1:left pattern X, segment length not decrease
      r1 = max(l_prev + a[i], max(r1_prev, r2_prev));
      // r2:left pattern X, segment length decrease
      r2 = max(l_prev, max(r1_prev, r2_prev - 1)) + a[i];
    } else {
      // l:left pattern O
      l = max(l_prev, r1_prev);
      // r1:left pattern X, segment length not decrease
      r1 = max(l_prev + a[i], r2_prev);
      // r2:left pattern X, segment length decrease
      r2 = max(l_prev, r1_prev) + a[i];
    }
    l_prev = l;
    r1_prev = r1;
    r2_prev = r2;
  }
  l = l_prev + a[a_len-1] ;
  r1 = r1_prev;
  r2 = r2_prev;
  return(max(l, max(r1, r2)));
}

int main(){
  cin >> n;
  cin >> s;
  long long l1 = 0;
  long long r1 = 0;
  long long c1 = 0;
  long long ioi = 0;
  long long tot = 0;
  vector<long long> tmpv;
  for (long long i=0;i<n;i++) {
    if (s[i] == '1') {
      c1++;
    } else {
      if (c1==0) {
	if (tmpv.size()>0)
	if (tmpv.size()>1) {
	  tot += solve(tmpv);
	}
	tmpv.clear();
      } else if (c1>0) {
	tmpv.push_back(c1);
      }
      c1 = 0;
    }
  }
  if (c1>0) 
    tmpv.push_back(c1);
  if (tmpv.size() > 1)
    tot += solve(tmpv);
  cout << tot << endl;
}

Submission Info

Judge Result