結果
問題 | No.544 Delete 7 |
ユーザー |
|
提出日時 | 2020-05-04 18:43:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 1,527 bytes |
コンパイル時間 | 1,001 ms |
コンパイル使用メモリ | 70,832 KB |
最終ジャッジ日時 | 2025-01-10 06:27:43 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 48 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:58:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | i64 N; scanf("%ld", &N); | ~~~~~^~~~~~~~~~~
ソースコード
#include <cstdint> #include <cstdio> #include <string> #include <vector> using namespace std; using i64 = int64_t; constexpr i64 inf = 987'654'321'987'654'321; int cmp(int x, int y) { if(x < y) { return 0; } if(x == y) { return 1; } return 2; } int next_state(int x, int y, int cur) { int res = cmp(x, y); if(res == 1) { res = cur; } return res; } // A + B == N i64 f(i64 x) { string s = to_string(x); int n = static_cast<int>(s.size()); // dp[AはNより][繰り上がったか] := Aの最小値 vector<vector<i64>> dp(3, vector<i64>(2, inf)); dp[1][0] = 0; i64 p10 = 1; for(int i=n-1; i>=0; --i) { vector<vector<i64>> ndp(3, vector<i64>(2, inf)); for(int state=0; state<3; ++state) { for(int carry=0; carry<2; ++carry) { if(dp[state][carry] == inf) { continue; } for(int ai=0; ai<10; ++ai) { for(int bi=0; bi<10; ++bi) { int ni = (carry + ai + bi) % 10; if(ni != s[i]-'0') { continue; } if(ai == 7 || bi == 7) { continue; } int nstate = next_state(ai, s[i]-'0', state); int ncarry = (carry + ai + bi) / 10; ndp[nstate][ncarry] = min(ndp[nstate][ncarry], ai*p10 + dp[state][carry]); } } } } p10 *= 10; dp = ndp; } i64 res = inf; for(int state=0; state<2; ++state) { res = min(res, dp[state][0]); } return res; } int main(void) { i64 N; scanf("%ld", &N); i64 a = f(N); i64 b = N - a; printf("%ld %ld\n", a, b); return 0; }