結果
問題 | No.1948 足し算するだけのパズルゲーム(1) |
ユーザー |
![]() |
提出日時 | 2022-05-20 23:14:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 1,636 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 175,924 KB |
実行使用メモリ | 19,200 KB |
最終ジャッジ日時 | 2024-09-20 09:37:27 |
合計ジャッジ時間 | 4,387 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2022.05.20 23:14:40 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; int main() { int h,w;cin >> h >> w; vector<vector<vector<ll>>> dp(h,vector<vector<ll>>(w,vector<ll>(2,-1))); vector<vector<ll>> a(h,vector<ll>(w)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> a[i][j]; } } dp[0][0][0] = a[0][0]; dp[0][0][1] = a[0][0]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (dp[i][j][0] != -1) { if (j+1 < w) { if (dp[i][j][0] > a[i][j+1]) dp[i][j+1][0] = max(dp[i][j+1][0],dp[i][j][0] + a[i][j+1]); if (i != h-1 || j+1 != w-1) dp[i][j+1][1] = max(dp[i][j+1][1],dp[i][j][0]); } if (i+1 < h) { if (dp[i][j][0] > a[i+1][j]) dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][0] + a[i+1][j]); if (i+1 != h-1 || j != w-1) dp[i+1][j][1] = max(dp[i+1][j][1],dp[i][j][0]); } } if (dp[i][j][1] != -1) { if (j+1 < w && dp[i][j][1] > a[i][j+1]) { dp[i][j+1][1] = max(dp[i][j+1][1],dp[i][j][1] + a[i][j+1]); } if (i+1 < h && dp[i][j][1] > a[i+1][j]) { dp[i+1][j][1] = max(dp[i+1][j][1],dp[i][j][1] + a[i+1][j]); } } } } if (dp[h-1][w-1][0] != -1 || dp[h-1][w-1][1] != -1) { puts("Yes"); } else { puts("No"); } return 0; }