結果

問題 No.3114 0→1
ユーザー moti
提出日時 2025-04-20 02:06:15
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 838 bytes
コンパイル時間 4,336 ms
コンパイル使用メモリ 132,608 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 02:06:21
合計ジャッジ時間 2,895 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); i++)
constexpr int INF = 1e9;

int dp[200001][2][2];

int main() {
  int N;
  string T;
  cin >> N >> T;

  int ans = INF;
  for (int q = 0; q < 2; q++) {
    string S = T;
    if (q > 1) reverse(S.begin(), S.end());
    rep(i, 200001) rep(j, 2) rep(k, 2) dp[i][j][k] = INF;
    if (S[0] == '0') {
      dp[0][1][0] = 0;
      dp[0][1][1] = 1;
    } else {
      dp[0][1][1] = 0;
    }
    rep(i, N-1) {
      dp[i+1][0][1] = dp[i][1][0] + (S[i+1] == '0');
      if (S[i+1] == '0') dp[i+1][1][0] = dp[i][1][1];
      dp[i+1][1][1] = min(dp[i][0][1] + (S[i+1] == '0'), dp[i][1][1] + (S[i+1] == '0'));
    }
    ans = min(ans, min(min(dp[N-1][0][1], dp[N-1][1][0]), dp[N-1][1][1]));
  }
  cout << ans << endl;
}
0