結果

問題 No.884 Eat and Add
コンテスト
ユーザー amaridekinai
提出日時 2019-09-14 05:13:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 1,000 ms
コード長 851 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 167,744 KB
実行使用メモリ 6,908 KB
最終ジャッジ日時 2024-07-05 01:24:33
合計ジャッジ時間 2,475 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

void chmin(ll &a, ll b){
  if( a > b){ swap(a,b); } return;}

int main(){
string N; cin >> N;
  ll m = (ll)N.size();
  if( m == 1){ cout << 1 << endl; return 0;}
  
  ll dp[200100][2];
  for(ll i = 0; i < 200100; i++){
    for(ll j = 0; j < 2; j++){ dp[i][j] = INF;}}
  reverse(N.begin(),N.end());
  
   if( N[0] == '0'){
     dp[1][0] = 0LL ;}
  else{
     dp[1][1] = 1LL; dp[1][0] = 1LL;}
       
  
  for(ll i = 1; i < m ; i++){
    if( N[i] == '0'){
      chmin(dp[i+1][0],dp[i][0]);
      chmin(dp[i+1][1], dp[i][1]+1);
      chmin(dp[i+1][0], dp[i][1]+1);}
    else{
      chmin(dp[i+1][1],dp[i][0]+1);
      chmin(dp[i+1][0],dp[i][0]+1);
      chmin(dp[i+1][1],dp[i][1]);}
  }
 
  cout << min(dp[m][0],dp[m][1]+1LL) << endl;
  
  return 0;}
0