結果
問題 |
No.1948 足し算するだけのパズルゲーム(1)
|
ユーザー |
![]() |
提出日時 | 2022-05-20 23:23:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 1,476 bytes |
コンパイル時間 | 1,598 ms |
コンパイル使用メモリ | 172,812 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-09-20 09:46:41 |
合計ジャッジ時間 | 4,032 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ int H,W; cin>>H>>W; vector<vector<int>> G(H,vector<int>(W)); for(int i=0;i<H;i++)for(int j=0;j<W;j++) cin>>G[i][j]; vector<vector<int>> dp(H,vector<int>(W,-1)),ddp(H,vector<int>(W,-1)); dp[0][0] = G[0][0]; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(i == 0 && j == 0) continue; int ans = -1; if(i != 0 && dp[i-1][j] > G[i][j]) ans = max(ans,dp[i-1][j]+G[i][j]); if(j != 0 && dp[i][j-1] > G[i][j]) ans = max(ans,dp[i][j-1]+G[i][j]); if(!(i==H-1 && j == W-1)){ int sub_ans = -1; if(i != 0 && dp[i-1][j] != -1 && dp[i-1][j] <= G[i][j]) sub_ans = max(sub_ans,dp[i-1][j]); if(j != 0 && dp[i][j-1] != -1 && dp[i][j-1] <= G[i][j]) sub_ans = max(sub_ans,dp[i][j-1]); ddp[i][j] = sub_ans; } dp[i][j] = ans; } } /*for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ cout<<dp[i][j]<<' '; } cout<<endl; }*/ if(dp[H-1][W-1] != -1 || ddp[H-1][W-1] != -1){ cout<<"Yes"<<endl; return 0; } for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(i == 0 && j == 0) continue; int ans = ddp[i][j]; if(i != 0 && G[i][j] < ddp[i-1][j]) ans = max(ans,ddp[i-1][j]+G[i][j]); if(j != 0 && G[i][j] < ddp[i][j-1]) ans = max(ans,ddp[i][j-1]+G[i][j]); ddp[i][j] = ans; } } if(ddp[H-1][W-1] != -1){ cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } }