結果
問題 | No.653 E869120 and Lucky Numbers |
ユーザー |
|
提出日時 | 2018-02-23 22:50:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,116 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 169,424 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-10 10:59:01 |
合計ジャッジ時間 | 2,436 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 WA * 1 |
ソースコード
#define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define MT make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() #define RT return #define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d)) #define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e)) using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vll = vector<ll>; // i<=20000 // dp[i桁まで見た][繰り上がりした][0,1,2個の値を使う] int dp[20004][2][3]; int dig[2] = { 6,7 }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); string p; cin >> p; each(c, p)c -= '0'; int N = sz(p); dp[0][0][2] = 1; rep(i, N) { int d = p[N-1-i]; rep(up, 2) { rep(num, 3) { int cur = dp[i][up][num]; if (!cur)continue; if (num == 2) { for (int x : dig)for (int y : dig) { int dd = (x + y + up) % 10; int nextUp = (x + y + up) / 10; if (dd == d) { dp[i + 1][nextUp][2] = 1; } } } if (num <= 2 && i > 0) { for (int x : dig) { int dd = (x + up) % 10; int nextUp = (x + up) / 10; if (dd == d) { dp[i + 1][nextUp][1] = 1; } } } if (up == d && i > 0) { dp[i + 1][0][0] = 1; } } } } string ans = "No"; rep(num, 2)if (dp[N][0][num])ans = "Yes"; cout << ans << endl; }