結果
問題 | No.3071 Double Speedrun |
ユーザー |
|
提出日時 | 2025-03-21 22:50:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 6,000 ms |
コード長 | 711 bytes |
コンパイル時間 | 2,097 ms |
コンパイル使用メモリ | 203,868 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 22:50:37 |
合計ジャッジ時間 | 2,777 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; #include<atcoder/modint> using namespace atcoder; using mint=modint998244353; ll H,W; vector<string> S; mint f(int a,int b,int A,int B){ vector<vector<mint>> DP(H,vector<mint> (W,0)); DP[a][b]=1; for(int h=0;h<H;h++){ for(int w=0;w<W;w++){ if(DP[h][w]==0)continue; if(h!=H-1&&S[h+1][w]!='#'){ DP[h+1][w]+=DP[h][w]; } if(w!=W-1&&S[h][w+1]!='#'){ DP[h][w+1]+=DP[h][w]; } } } return DP[A][B]; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin>>H>>W; S.resize(H); for(int i=0;i<H;i++)cin>>S[i]; mint an=f(0,1,H-2,W-1)*f(1,0,H-1,W-2)-f(0,1,H-1,W-2)*f(1,0,H-2,W-1); cout<<an.val()<<endl; }