結果
問題 | No.884 Eat and Add |
ユーザー | erbowl |
提出日時 | 2020-03-20 10:57:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 678 bytes |
コンパイル時間 | 1,640 ms |
コンパイル使用メモリ | 171,836 KB |
実行使用メモリ | 14,648 KB |
最終ジャッジ日時 | 2024-05-08 03:51:19 |
合計ジャッジ時間 | 2,402 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 23 ms
14,492 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 23 ms
14,376 KB |
testcase_07 | AC | 23 ms
14,392 KB |
testcase_08 | AC | 23 ms
14,376 KB |
testcase_09 | AC | 23 ms
14,332 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
ソースコード
typedef long long ll; #include <bits/stdc++.h> using namespace std; int main() { string s; std::cin >> s; ll n = s.length(); // i桁目までみたときのコスト、jは繰り上がっているかフラグ vector<vector<ll>> dp(n+1,vector<ll>(2,0)); dp[0][0]=dp[0][1]=(s[n-1]=='1'); for (int i = 1; i < n; i++) { ll now = n-i-1; if(s[now]=='1'){ dp[i][1] = min(dp[i-1][0]+1,dp[i-1][1]); dp[i][0] = dp[i-1][0]+1; }else{ dp[i][1] = dp[i-1][1]+1; dp[i][0] = min(dp[i-1][0],dp[i-1][1]+1); } } std::cout << min(dp[n-1][1]+1,dp[n-1][0]) << std::endl; }