結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー cho435
提出日時 2025-03-21 23:54:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 785 ms / 6,000 ms
コード長 1,318 bytes
コンパイル時間 4,277 ms
コンパイル使用メモリ 256,704 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 23:54:45
合計ジャッジ時間 11,626 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <typename T> bool chmin(T &x, T y) {
	return x > y ? (x = y, true) : false;
}
template <typename T> bool chmax(T &x, T y) {
	return x < y ? (x = y, true) : false;
}

struct IOST {
	IOST() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(20);
	}
} IOST;

using mint = atcoder::modint998244353;

int main(){
	int h,w;
	cin>>h>>w;
	vector<string> s(h);
	rep(i,0,h) cin>>s[i];
	vector<vector<mint>> dp(w+1,vector<mint>(w+1));
	rep(i,1,w){
		if(s[0][i]=='#') break;
		dp[0][i]=1;
	}
	rep(i,1,h){
		vector<vector<mint>> ndp(w+1,vector<mint>(w+1));
		vector<int> nx(w,-1);
		for(int j=w-1;j>=0;j--){
			if(s[i][j]=='#') continue;
			nx[j]=j;
			if(j+1<w) chmax(nx[j],nx[j+1]);
		}
		rep(a,0,w) rep(b,a+1,w){
			if(i==h-1&&b!=w-1) continue;
			int mxa=min(nx[a]+1,(int)b);
			int mxb=nx[b]+1;
			if(mxa<=a||mxb<=b) continue;
			ndp[a][b]+=dp[a][b];
			ndp[mxa][b]-=dp[a][b];
			ndp[a][mxb]-=dp[a][b];
			ndp[mxa][mxb]+=dp[a][b];
		}
		rep(a,0,w) rep(b,0,w+1){
			ndp[a+1][b]+=ndp[a][b];
		}
		rep(a,0,w+1) rep(b,0,w){
			ndp[a][b+1]+=ndp[a][b];
		}
		swap(ndp,dp);
	}
	cout<<dp[w-2][w-1].val()<<"\n";
}
0