結果
問題 | No.1948 足し算するだけのパズルゲーム(1) |
ユーザー |
|
提出日時 | 2022-05-21 00:15:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 2,241 ms |
コンパイル使用メモリ | 201,052 KB |
最終ジャッジ日時 | 2025-01-29 12:17:30 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _RUTHEN #include "debug.hpp" #else #define show(...) true #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) template <class T> using V = vector<T>; int main() { ios::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; V<V<ll>> A(H, V<ll>(W)); rep(i, H) rep(j, W) cin >> A[i][j]; V<V<V<ll>>> dp(H, V<V<ll>>(W, V<ll>(2, 0))); dp[0][0][0] = A[0][0]; rep(i, H) { rep(j, W) { if (i + 1 < H) { rep(k, 2) { if (dp[i][j][k] > A[i + 1][j]) { dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + A[i + 1][j]); } else { if (k == 0) { dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][0]); } } } } if (j + 1 < W) { rep(k, 2) { if (dp[i][j][k] > A[i][j + 1]) { dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k] + A[i][j + 1]); } else { if (k == 0) { dp[i][j + 1][1] = max(dp[i][j + 1][1], dp[i][j][0]); } } } } } } cout << (max(dp[H - 1][W - 1][0], dp[H - 1][W - 1][1]) > A[H - 1][W - 1] ? "Yes" : "No") << '\n'; return 0; }