#373612 (C++14) No.884 Eat and Add

• 問題: No.884 Eat and Add
• ユーザー: e869120
• 提出日時: 2019-08-30 20:16:27
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 10 ms / 1,000 ms
• コード長: 863 bytes
• コンパイル時間: 652 ms
• コンパイル使用メモリ: 67,808 KB
• 実行使用メモリ: 5,984 KB
• 最終ジャッジ日時: 2023-08-14 01:15:43
• 合計ジャッジ時間: 1,671 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	9 ms; 5,792 KB
testcase_04	AC	10 ms; 5,984 KB
testcase_05	AC	10 ms; 5,956 KB
testcase_06	AC	9 ms; 5,828 KB
testcase_07	AC	8 ms; 5,860 KB
testcase_08	AC	9 ms; 5,844 KB
testcase_09	AC	9 ms; 5,888 KB
testcase_10	AC	2 ms; 4,380 KB
testcase_11	AC	1 ms; 4,376 KB

ソースコード

#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;

string S;
int A[1 << 18], dp[1 << 18][2];

int main() {
	cin >> S; assert(1 <= S.size() && S.size() <= 200000 && S[0] == '1');
	for (int i = 0; i < S.size(); i++) assert(S[i] == '0' || S[i] == '1');
	for (int i = 0; i < S.size(); i++) A[S.size() - 1 - i] = (S[i] - '0');
	for (int i = 0; i <= S.size() + 1; i++) { dp[i][0] = (1 << 30); dp[i][1] = (1 << 30); }

	dp[0][0] = 0;
	for (int i = 0; i <= S.size(); i++) {
		for (int j = 0; j < 2; j++) {
			if (dp[i][j] == (1 << 30)) continue;

			for (int k = 0; k < 2; k++) {
				int ret = 0;
				if ((A[i] + j + k) % 2 == 1) ret++;
				if (k == 1) ret++;

				int s = 0; if (A[i] + j + k >= 2) s = 1;
				dp[i + 1][s] = min(dp[i + 1][s], dp[i][j] + ret);
			}
		}
	}
	cout << dp[S.size() + 1][0] << endl;
	return 0;
}