結果
問題 |
No.1948 足し算するだけのパズルゲーム(1)
|
ユーザー |
![]() |
提出日時 | 2022-05-20 21:48:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,134 bytes |
コンパイル時間 | 4,029 ms |
コンパイル使用メモリ | 254,548 KB |
最終ジャッジ日時 | 2025-01-29 10:27:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main() { int H,W; cin>>H>>W; vector a(H,vector<int>(W)); rep(i,H){ rep(j,W)cin>>a[i][j]; } vector dp(H,vector(W,vector<int>(2,-Inf))); dp[0][0][0] = a[0][0]; rep(i,H){ rep(j,W){ rep(k,2){ if(i!=H-1){ int ii = i+1,jj = j; if(dp[i][j][k] > a[ii][jj]){ dp[ii][jj][k] = max(dp[ii][jj][k],min(Inf,dp[i][j][k]+a[ii][jj])); } else{ if(k==0 && (ii!=H-1 || jj!=W-1)){ dp[ii][jj][1] = max(dp[ii][jj][1],dp[i][j][k]); } } } if(j!=W-1){ int ii = i,jj = j+1; if(dp[i][j][k] > a[ii][jj]){ dp[ii][jj][k] = max(dp[ii][jj][k],min(Inf,dp[i][j][k]+a[ii][jj])); } else{ if(k==0 && (ii!=H-1 || jj!=W-1)){ dp[ii][jj][1] = max(dp[ii][jj][1],dp[i][j][k]); } } } } } } int ans = max(dp[H-1][W-1][0],dp[H-1][W-1][1]); if(ans==-Inf)cout<<"No"<<endl; else cout<<"Yes"<<endl; return 0; }