Submission #950878

#TimeUsernameProblemLanguageResultExecution timeMemory
950878Soshi85Tents (JOI18_tents)C++17
100 / 100
70 ms70996 KiB
//#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll, ll>; using piii = pair<ll, pii>; #define pb push_back #define F first #define S second #define len(x) (int)x.size() #define all(x) x.begin(),x.end() #define file freopen("connect.in", "r", stdin);freopen("connect.out", "w", stdout); #define kill(x) {cout << x << '\n'; continue;} #define int long long const int maxn = 3e3 + 5, maxm = 2e5, LG = 20, MOD = 1e9+7;// 998244353 const ll inf = 6e18; //priority_queue< int, vector<int>, greater<int>> pq; min heap //priority_queue< int, vector<int>, less<int> > pq; max heap mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int h, w, dp[maxn][maxn]; signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> h >> w; for(int i = 0; i <= h; ++i) dp[i][0] = 1; for(int i = 0; i <= w; ++i) dp[0][i] = 1; dp[1][1] = 5; for(int i = 2; i <= max(h, w); ++i) { dp[1][i] = 4 + i-1 + dp[1][i-1]; dp[1][i] %= MOD; dp[i][1] = dp[1][i]; } for(int i = 2; i <= h; ++i) for(int j = 2; j <= w; ++j) { dp[i][j] = (4 * j * dp[i-1][j-1] % MOD); dp[i][j] += ((j*(j-1)/2 % MOD) * dp[i-1][j-2] % MOD) % MOD; dp[i][j] += ((j*(i-1) % MOD) * dp[i-2][j-1] % MOD) % MOD; dp[i][j] += dp[i-1][j]; dp[i][j] %= MOD; } cout << dp[h][w] - 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...