Submission #1691348

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	string s;
	cin >> s;
	s += "00";
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (s[i] == '1') {
			for (int j = i; j < N; j++) {
				if (s[j + 1] == s[j + 2] && s[j + 1] == '0') {
					int box = 0;
					vector<int>place;
					for (int k = i; k <= j; k++) {
						if (s[k] == '0') {
							box++;
							place.push_back(k);
						}
					}
					if (box == 0) {
						i = j + 1;
						break;
					}
					if (box == 1) {
						ans += max(j - place[0], place[0] - i);
						//	cout << ans << endl;
						i = j + 1;
						break;
					}
					vector<int>bf(box);
					vector<int>nx(box);
					bf[0] = place[0] - i;
					nx[0] = place[1] - place[0] - 1;
					for (int k = 1; k < box - 1; k++) {
						bf[k] = nx[k - 1];
						nx[k] = place[k + 1] - place[k] - 1;
					}
					bf[box - 1] = nx[box - 2];
					nx[box - 1] = j - place[box - 1];
					vector<vector<int>>dp(box, vector<int>(5, 0));
					if (nx[0] > 1) {
						dp[0][0] = bf[0];
					}
					else {
						dp[0][1] = bf[0];
					}
					dp[0][2] = nx[0];
					if (nx[0] > 1) {
						dp[0][3] = nx[0] - 1;
					}
					for (int k = 1; k < box; k++) {
						if (nx[k] > 1) {
							dp[k][0] = max({ dp[k - 1][0] - 1 + bf[k], dp[k - 1][4] + bf[k] ,dp[k - 1][3] + 1 });
						}
						else {
							dp[k][1] = max(max(dp[k - 1][0] - 1, dp[k - 1][4]) + bf[k], dp[k - 1][3] + 1);
						}
						dp[k][2] = max({ dp[k - 1][0],dp[k - 1][3],dp[k - 1][4] }) + nx[k];
						if (nx[k] > 1) {
							dp[k][3] = dp[k][2] - 1;
						}
						dp[k][4] = max({ dp[k - 1][0],dp[k - 1][1],dp[k - 1][2],dp[k - 1][3],dp[k - 1][4] });
					}
					ans += max({ dp[box - 1][0],dp[box - 1][1],dp[box - 1][2],dp[box - 1][3],dp[box - 1][4] });
					//	cout << ans << endl;
					i = j + 1;
					break;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result