Submission #1691655

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int N;
string S;
int dp[500001];

int main()
{
  cin >> N;
  cin >> S;

  for(int i = 0; i < S.size(); i++) {

    int ret = dp[i];

    if(S[i] == '1') {

      // 1111101 型
      if(i > 0 && S[i - 1] == '0') {
        for(int j = i - 2; j >= 0; j--) {
          if(S[j] == '0') break;
          ret = max(ret, dp[j] + (i - 1) - j);
        }
      }

      // 1011111 型
      {
        int j = i;
        while(j >= 0 && S[j] == '1') --j;
        if(j >= 1 && S[j] == '0' && S[j - 1] == '1') {
          ret = max(ret, dp[j - 1] + i - j);
        }
      }

    }

    dp[i + 1] = ret;
  }

  cout << dp[S.size()] << endl;
}

Submission Info

Judge Result