結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー cho435
提出日時 2025-03-21 23:16:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,134 bytes
コンパイル時間 4,662 ms
コンパイル使用メモリ 260,856 KB
実行使用メモリ 21,016 KB
最終ジャッジ日時 2025-03-21 23:16:52
合計ジャッジ時間 11,789 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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];
	map<pair<int,int>,mint> dp;
	rep(i,1,w){
		if(s[0][i]=='#') break;
		dp[{0,i}]=1;
	}
	rep(i,1,h){
		map<pair<int,int>,mint> ndp;
		vector<vector<int>> nx(w);
		for(int j=w-1;j>=0;j--){
			if(s[i][j]=='#') continue;
			nx[j].push_back(j);
			if(j+1<w) for(int bf:nx[j+1]) nx[j].push_back(bf);
		}
		for(auto[p,ad]:dp){
			auto[a,b]=p;
			if(i==h-1&&b!=w-1) continue;
			for(auto nb:nx[b]) for(auto na:nx[a]){
				if(b<=na) break;
				if(nb<=na) break;
				ndp[{na,nb}]+=ad;
			}
		}
		swap(ndp,dp);
	}
	cout<<dp[{w-2,w-1}].val()<<"\n";
}
0