Submission #1082753

#TimeUsernameProblemLanguageResultExecution timeMemory
1082753toast12Tents (JOI18_tents)C++14
100 / 100
234 ms72588 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MOD = 1e9+7; vector<vector<bool>> ready; vector<vector<ll>> dp; // there are h rows and w columns left ll solve(int h, int w) { if (h < 0 || w < 0) return 0; if (h == 0 || w == 0) return 1; if (ready[h][w]) return dp[h][w]; ll ans = 0; // place nothing ans += solve(h-1, w); ans %= MOD; // place one tent in this row // this eliminates one row, one column, and there are 4 different directions the opening can be ans += 4*solve(h-1, w-1)*w; ans %= MOD; // place two tents in this row // this eliminates one row, two columns and you can place the two tents in w choose 2 different ways ans += solve(h-1, w-2)*(w*(w-1)/2); ans %= MOD; // place two tents in one column, but one of them is in this row // this eliminates two rows, one column and you can choose the column w ways and choose the other row (h-1) ways ans += solve(h-2, w-1)*w*(h-1); ans %= MOD; ready[h][w] = true; return dp[h][w] = ans; } int main() { int h, w; cin >> h >> w; ready.resize(h+1, vector<bool>(w+1)); dp.resize(h+1, vector<ll>(w+1)); cout << (solve(h, w)+MOD-1) % MOD << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...